ela

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.

What it prints
disc 1: A to C
disc 2: A to B
disc 1: C to B
disc 3: A to C
disc 1: B to A
disc 2: B to C
disc 1: A to C
3 discs in 7 moves