Tutorial, lesson 6 of 9
Recursion
The Tower of Hanoi has three pegs and a stack of discs on the first, largest at the bottom. The
discs go to the third peg, one at a time, never a larger one on a smaller. Moving n discs is
three steps: the n - 1 above the largest go to the spare peg, the largest goes across, then the
n - 1 go back on top of it. Moving n - 1 is the same puzzle, one disc smaller.
hanoi is those three steps. It calls itself for the smaller puzzle, and a puzzle of no discs
needs no moves, so if $n == 0; return 0 is where the calls stop.
Each call has its own parameters and variables: the before of one call is not the before of
the call inside it. A proc sees its parameters and the constants, as lesson 3 said, so nothing
one call sets reaches another except what it returns.
The pegs change places from call to call: the spare peg of one call is the target of the next.
Follow disc 1 in the output, and it moves every other line.
Try hanoi(4, "A", "C", "B"): every disc added doubles the moves, plus one.
Then try hanoi(500, "A", "C", "B"). The calls nest 500 deep before the first move, and a page
holds 400, so the run stops at the call past that with an error naming the proc,
recursion deeper than 400 calls in hanoi, never a crash. Installed ela holds about 7,000.