The idea: move n−1, move the big disk, move n−1

The puzzle has three pegs, A, B and C, and n disks of different sizes stacked on A, the biggest at the bottom. The goal is to move them all to C. You move one disk at a time, always the top disk of a peg, and you may never put a bigger disk on a smaller one. The recursive solution splits the job for n disks into three steps: move the n−1 smaller disks out of the way to the spare peg, move the biggest disk to the target, then move the n−1 disks back on top of it.

Four snapshots for 3 disks. Start: disks 3, 2, 1 on A. After step 1, hanoi(2, A, B, C): disk 3 on A, disks 2 and 1 on B. After step 2, move disk 3: disk 3 on C. After step 3, hanoi(2, B, C, A): disks 3, 2, 1 on C
Steps 1 and 3 are the same puzzle with one disk less; only step 2 moves a disk itself.

The code

def hanoi(n, src, dst, via):
    if n == 1: move(1, src, dst); return
    hanoi(n - 1, src, via, dst)   # step 1
    move(n, src, dst)             # step 2
    hanoi(n - 1, via, dst, src)   # step 3

hanoi(3, "A", "C", "B")

The base case is one disk: it is moved directly, with no more calls (Demo: 1 disk). With two disks the code moves disk 1 to B, disk 2 to C and disk 1 to C: small, big, small (Demo: 2 disks). The peg names rotate between calls: in step 1 the spare peg becomes the target, and in step 3 the source becomes the spare.

Trust the recursive call

To write hanoi(n) you do not need to know how hanoi(n−1) does its work. You only need to know what it does: it moves n−1 disks from one peg to another and never breaks the rule. Disk n is bigger than all of them, so it never gets in their way. This is the recursive leap of faith: if the base case is right and each call works on a smaller problem, the whole thing is right, by induction on n.

The view top call only shows this. Only hanoi(n) is traced; each hanoi(n−1) is a green frame and its disks move as one tower (Demo: 4 disks, top call only). The view every call traces everything, and the stack shows the steps each frame is waiting on (Demo: 3 disks).

Counting the moves: 2n − 1

Let T(n) be the number of moves for n disks. Steps 1 and 3 take T(n−1) each, step 2 takes one move:

T(1) = 1,   T(n) = 2·T(n−1) + 1,   so T(n) = 2n − 1.

Disks nMoves 2n − 1At one move per second
377 seconds
53131 seconds
101,02317 minutes
201,048,57512 days
64about 1.8 × 1019about 585 billion years

No method does better: disk n has to move at least once, and before it moves, all n−1 smaller disks must be stacked on the third peg. So 2n − 1 is the minimum, and the recursive solution reaches it (Demo: 5 disks, top call only).

Call tree for hanoi(3, A, C, B): the root moves disk 3 as move 4; its children hanoi(2, A, B, C) and hanoi(2, B, C, A) move disk 2 as moves 2 and 6; four leaves hanoi(1, …) move disk 1 as moves 1, 3, 5 and 7
Each call makes exactly one move, so 7 calls give 7 moves; reading the tree left to right gives the order.

The call stack is only n frames deep

There are 2n − 1 calls in all, but they do not all wait at once. A call waits on the stack only while its own step 1 or step 3 runs, so the stack holds one frame per disk size: at most n frames. Time grows as O(2n), stack space only as O(n). Factorial has the same depth for a different reason: one call per level, see Recursive Factorial; the page Tail Calls and Tail-Call Optimization shows what that depth costs. Hanoi makes two calls per level, like the choice trees in Permutations and Subsets, but it never backtracks.

The recursive leap of faith is a proof by induction on n; Proof by Induction shows the base case and the inductive step as falling dominoes.

What the page leaves out

The canvas stops at 5 disks. It leaves out the iterative solution (move the smallest disk one peg around in a fixed direction every other move, and make the only other legal move in between), the link to the binary reflected Gray code (move k moves the disk whose bit changes), and puzzles with four or more pegs (the Frame–Stewart algorithm), where the minimum number of moves is a much harder question.