A First Taste of Algorithms · The Procedure That Calls Itself

Why this is not cheating

“To move a tower, move a tower” sounds like the dictionary that defines a word using the word. The suspicion is correct in general and wrong here, and the difference is worth nailing down, because it is the difference between recursion and nonsense.

Two things rescue the definition. First, every self-call is strictly smaller: n hands its work to n − 1, never to n or upward. Second, the descent has a floor: at n = 1 the procedure does its work directly, asking nobody. Smaller-every-time plus a floor means the chain of delegations cannot go on forever — n, n − 1, n − 2, … must hit 1, the floor acts, and the answers come climbing back up the chain. A recursion with both properties is as legitimate as any procedure in this book; a recursion missing either is an infinite regress, and in Lab 3 you will build one on purpose and watch the machine refuse it.

If “smaller every time, with a floor” sounds familiar, it should. It is induction, from Book 2, read in the opposite direction. Induction climbs up: the statement holds at 1, and each rung passes truth to the next. Recursion climbs down: the case at n hands its work toward 1, where work becomes possible. They are the same staircase. And that means proving a recursive procedure correct is induction with no disguise at all: the procedure is correct for n = 1 (look at it); and if it is correct for n − 1, then the three-line plan — clear, cross, restack — is legal and correct for n. Notice your old friend: true at the floor, preserved at each level, decisive at the top. Same trick as Chapter 1’s invariant and Chapter 2’s stays-ahead. Still the only trick.

The bill

Two questions, always. Correctness is settled. Now the cost, in the declared currency of moves. Let M(n) be the moves our procedure makes on n disks. Read the three-line plan and the bill writes itself:

M(n) = 2·M(n − 1) + 1, with M(1) = 1.

A cost equation that refers to itself — of course it does; the procedure refers to itself. Such an equation is called a recurrence, and the cheapest way to understand one is to make it produce numbers:

Stare until the pattern declares itself: each entry is one less than a power of two. M(n) = 2ⁿ − 1. (Conjectured from the table; proved, in two lines of induction, in Fluency 1.3 — by now you know that a table is a conjecture machine, not a proof.)

Sit with what this kind of growth means, because it is the opposite of Chapter 1’s logarithm. There, multiplying the problem added to the cost. Here, adding one disk doubles the cost. The logarithm and the exponential are the two ends of the book’s scale — the curve you want to be on, and the wall. Ten disks, about a thousand moves: an evening. Twenty disks, about a million: a sleepless month at one move per second. Sixty-four disks — hold that thought.

A human moment

The Tower of Hanoi is not ancient. It was invented in 1883 by Édouard Lucas — a French number theorist with serious theorems to his name — and sold in toy shops, credited to a mysterious “Professor N. Claus (de Siam), mandarin of the College of Li-Sou-Stian.” Read those names again slowly: N. Claus de Siam is an anagram of Lucas d’Amiens — Lucas of Amiens, his hometown — and “Li-Sou-Stian” rearranges the Lycée Saint-Louis, where he taught. The toy shipped wrapped in a legend, also written by Lucas: in a temple at Benares, priests labor over a tower of 64 golden disks, and when the last disk falls, the world ends.

The legend is marketing. Its arithmetic is real, and it is the whole reason to tell the story. By your own formula the priests need 2⁶⁴ − 1 moves — 18,446,744,073,709,551,615 of them. At one move per second, day and night, that is about 585 billion years: more than forty times the age of the universe. Lucas knew exactly what he was doing — he dressed the scariest curve in mathematics as a children’s toy, signed it with a puzzle, and let the customers discover the apocalypse by themselves. The pseudonym was solved; the curve never softened. When someone tells you a process is “just like Hanoi but bigger,” check which axis got bigger before you agree to wait.

All 32 chapters of A First Taste of Algorithms · Foundations · All courses