Numbers & Functions · 7 Functions as Objects

7.4 Doing it again: iteration

There’s one special kind of composition so important it deserves its own name. What if you chain a machine to itself — feed its output straight back into its own funnel, and repeat?

x →f(x) →f(f(x)) →f(f(f(x))) →· · · This is iteration, and it is one of the most powerful ideas in all of computation — half of what computers do is iterate. When a machine is defined in terms of itself this way, programmers call it recursion.

f input output feeds back 0 2 4 6 step 0 10 20 30 value attractor: 0 iterating f(x) = x/2 from 32 Figure 7.5. Iteration is a feedback loop: the machine’s output curves back into its own funnel. Iterating f(x) = x/2 from 32 marches steadily toward 0 — the attractor.

Let’s iterate a few machines by hand and watch the long-run behavior, because the long run is the whole point: • Halve it, f(x) = x 2, from 16: 16, 8, 4, 2, 1, 1 2, . . . — marches toward 0 and never quite arrives. We call 0 an attractor.

• Multiply by 2, from 1: 1, 2, 4, 8, . . . — runs off to infinity. The behavior flipped just by changing the machine.

• Average x with 2 x, from any positive number: it homes in, startlingly fast, on √ 2. From x = 1: 1.5, then 1.4166 . . . , then 1.41421 . . . — the irrational number from Chapter 2, appearing as the destination of an iteration. 0 1 2 3 4 step 1.30 1.35 1.40 1.45 1.50 1.55 value 1.5 1.41667 1.41422 1.41421 p 2 = 1.41421 the p 2-finder homes in after just a few steps Figure 7.6. The √ 2-finder converging. Iterating f(x) = 1 2 x + 2 x
lands on √ 2 in just a few steps — the ancestor of Newton’s method and gradient descent.

Iteration is how you solve things you can’t solve directly. You can’t write √ 2 as a fraction — but you can write a simple machine whose repeated application converges to it, as close as you like.

In the calculus book you’ll meet Newton’s method, which iterates a clever machine to hunt down the roots of any equation. In the machine-learning book you’ll meet gradient descent — the algorithm that actually trains every neural network — and it, too, is pure iteration: take a step downhill, look again, repeat a few million times. The training of every AI you’ve ever used is one machine, iterated. Hold that thread tightly.

Functions as Objects ▶Run it yourself — type any number and watch it find √ 2. (notebook 7.1 in Colab) Type any positive starting number and predict where the √ 2-finder ends up before you run it — it always lands on √ 2, no matter where you start.

Then swap the 2 for any other number and discover you’ve built a machine that finds square roots. This is the seed of how every AI is trained.

All 8 chapters of Numbers & Functions · Foundations · All courses