Chapter 2 · Analysis Framework
Tower of Hanoi
Move the whole stack from peg A to peg C, one disk at a time, never putting a bigger disk on a smaller one. The recursive solution needs exactly 2ⁿ − 1 moves, and you can watch every call that produces them.
Mode
Keyboard: ← → step, space play/pause.
Click a peg to pick up its top disk, then click where it goes. Keys: 1 / 2 / 3 (or A / B / C).
disk that just moved
call on the stack
call making the current move
finished call
not called yet
Recursion tree (one node per call, laid out in move order)
How to read this
- Pegs: disk k is labeled k; bigger number = bigger disk. The red outline marks the disk that just moved, and the arrow shows where it came from.
- Recursion tree: each node is one call Hanoi(k, from→to). Its left child moves the k − 1 smaller disks out of the way, the node itself moves disk k, and its right child moves the k − 1 disks back on top. Reading the nodes left to right gives the moves in order, which is why every node sits exactly above its own move.
- Call stack: the chain of calls that are still unfinished. Its height is at most n, even though there are 2ⁿ − 1 calls in total: time is exponential, memory is linear.
- Counters: the moves so far next to 2ⁿ − 1, the number that the recurrence M(n) = 2M(n−1) + 1, M(1) = 1 predicts.
Try this
- Watch n = 3 and write down the 7 moves. Then switch to "Play it yourself" and reproduce them from memory.
- With n = 4, pause right after disk 4 moves (move 8). Where are disks 1–3? (All on peg B: exactly what the first recursive call promised.)
- Notice that disk 1 moves on every odd-numbered move, always cycling in the same direction. Can you use this to solve n = 5 by hand?
- Play n = 4 yourself and try to finish in fewer than 15 moves. You can't: 2ⁿ − 1 is also a lower bound. The biggest disk must move at least once, and just before that the n − 1 smaller disks must all sit on the third peg, which already costs 2ⁿ⁻¹ − 1 moves, and the same again afterwards.
- Slide n from 1 to 8 and watch the tree double each time: 1, 3, 7, 15, …, 255 calls.