There are three rods, A, B and C. Rod A holds n discs of different sizes, stacked with the biggest at the bottom and the smallest on top. Move the whole stack to rod C. Three rules:
Move only one disc at a time.
Only the top disc of a rod can be moved.
Never put a bigger disc on top of a smaller one.
Print the moves, and say how many moves are needed for n discs.
The French mathematician Édouard Lucas sold it as a toy puzzle in 1883. He packaged it with a made-up legend. In a temple, priests move 64 golden discs between three diamond needles, one move per second, following these rules. When they finish, the world will end. Below, we work out how long that would take.
It asks whether you can trust recursion. The moves for even 4 discs are hard to find by trial and error. But the idea is three lines long, as soon as you stop thinking about individual moves and think about the whole stack.
Think about the biggest disc. To move it from A to C, two things must be true at that moment:
It must be the only disc on A. Nothing can sit on top of it.
C must be empty. Otherwise the biggest disc would land on a smaller one.
So every other disc, all n - 1 of them, must be sitting on B. That tells us the whole plan.
Move the top n - 1 discs from A to B, using C as the spare.
Move the biggest disc from A to C.
Move the n - 1 discs from B to C, using A as the spare.
Moving 3 discs. Step ① moves the top two discs out of the way onto B. Step ② moves the biggest disc to C in a single move. Step ③ moves the two discs from B onto it. Steps ① and ③ are each the 2-disc puzzle, with the rods playing different roles.
Steps 1 and 3 are the same puzzle with one disc fewer. Only the rods have changed roles. That is recursion: a problem that contains smaller copies of itself. And the smallest copy is easy. With zero discs, there is nothing to do.
Notice that step 1 does not break the rules for the biggest disc. While the n - 1 smaller discs move around, the biggest disc sits at the bottom of A, and every disc is smaller than it. So it never gets in the way, and never blocks a legal move.
move disc 1 from A to Cmove disc 2 from A to Bmove disc 1 from C to Bmove disc 3 from A to Cmove disc 1 from B to Amove disc 2 from B to Cmove disc 1 from A to C7
(1) The base case. No discs means no moves. Some versions stop at n == 1 and print one move instead. Both work. Stopping at 0 is shorter and avoids repeating the "print a move" line.
(2) Step 1. Move n - 1 discs off the top, from source to spare. In this smaller puzzle, the discs go to the spare rod, and the real target rod is free to use as a helper. So the two rods swap places in the call.
(3) Step 2. Move disc n, the biggest in this call, straight from source to target. Discs are numbered 1 (smallest) to n (biggest).
(4) Step 3. Move the n - 1 discs from spare onto target. Now source is the free rod.
How to read a recursive function without getting lost. Do not try to follow every call down to the bottom. Check two things only. First, the base case is right: zero discs, zero moves. Second, if the smaller calls work, the bigger call works. Step 2 is one legal move, and steps 1 and 3 are smaller puzzles that we trust. If both checks pass, the function works for every n. This way of reasoning is called mathematical induction. It is the same reason a row of dominoes falls: the first falls, and each one knocks over the next.
For n = 3, here is how the calls nest. Each indented line is a call made by the line above it.
hanoi(3, A→C) hanoi(2, A→B) hanoi(1, A→C) → move disc 1 A to C move disc 2 A to B hanoi(1, C→B) → move disc 1 C to B move disc 3 A to C hanoi(2, B→C) hanoi(1, B→A) → move disc 1 B to A move disc 2 B to C hanoi(1, A→C) → move disc 1 A to C
The seven moves come out in exactly the order printed above. Disc 3 moves once, in the middle. Disc 2 moves twice. Disc 1 moves four times.
Call the number of moves for n discs T(n). The code does two smaller puzzles and one move.
T(0) = 0, \qquad T(n) = 2\,T(n - 1) + 1
Read it aloud: "the moves for n discs are twice the moves for n - 1 discs, plus one." Work out the first few values.
n
T(n)
1
2 \times 0 + 1 = 1
2
2 \times 1 + 1 = 3
3
2 \times 3 + 1 = 7
4
2 \times 7 + 1 = 15
5
2 \times 15 + 1 = 31
Each value is one less than a power of two. So T(n) = 2^n - 1.
Checking that the formula is right. It holds for n = 0, since 2^0 - 1 = 0. And if T(n - 1) = 2^{n-1} - 1, then T(n) = 2(2^{n-1} - 1) + 1 = 2^n - 2 + 1 = 2^n - 1. The formula passes the same two induction checks as the code.
Can any method do it in fewer moves? No. The biggest disc must move at least once. Before its first move, the other n - 1 discs must all be on the spare rod, which takes at least T(n - 1) moves. After its last move, they must all come back on top of it, which takes at least T(n - 1) more. So at least 2\,T(n-1) + 1 moves are needed, which is exactly what the recursion does. 2^n - 1 is the smallest number possible.
The end of the world. For 64 discs: 2^{64} - 1 = 18{,}446{,}744{,}073{,}709{,}551{,}615 moves. At one move per second, that is about 585 billion years. The universe is only about 13.8 billion years old, so the world is safe for a very long time.
Time:O(2^n). Each extra disc doubles the work. This is unavoidable, because the output itself has 2^n - 1 moves.
Memory:O(n) for the recursion stack. The calls go n levels deep, one for each disc, and only one chain of calls is open at a time. The list of moves is extra, O(2^n), but only because we chose to store it. Printing as you go would need just the O(n) stack.
Compare this with naive Fibonacci in 4.0.8. Both make two recursive calls and both take exponential time. But Fibonacci's two calls overlapped and repeated work, so memoisation fixed it. Hanoi's two calls do different work, moving different discs to different places. Nothing repeats, so nothing can be saved. Exponential time is the true cost here.
Look at the printed moves. Disc 1 moves on every odd-numbered move: moves 1, 3, 5 and 7. And it always goes around the rods in the same direction. For an odd number of discs that direction is A → C → B → A. For an even number it is A → B → C → A. On every even-numbered move, there is exactly one legal move that does not involve disc 1. This gives a way to solve the puzzle without recursion at all, using a simple loop.
These are the questions that usually come right after you solve it. Each one has a short, plain answer you can say out loud.
"Explain why the recursion works." To move the biggest disc, every other disc must be on the spare rod. So move the other n - 1 discs there first, move the biggest disc, then move the n - 1 discs back on top.
"How many moves for n discs?"2^n - 1. Each extra disc doubles the moves and adds one: T(n) = 2T(n - 1) + 1. No method can use fewer moves.
"How much memory does it use?"O(n), for the calls waiting on the stack. Only one chain of calls is open at a time, and it is n calls deep.
"Can memoisation make it faster?" No. The two recursive calls move different discs to different places. Nothing is repeated, so there is nothing to save.
"Can you solve it without recursion?" Yes. Disc 1 moves on every odd-numbered move, always in the same direction. On every even-numbered move, there is only one legal move that does not use disc 1.
One thing to volunteer: "To check a recursive function, I only check two things: the base case, and that a step works if the smaller steps work."