Towers of Hanoi
mediumAssume you can already move n−1 disks and the algorithm writes itself. Believing the smaller case is exactly what makes recursion work, and exactly what makes it hard to learn.
O(2ⁿ)Space O(n)Saved in this browser - no sign-up, nothing sent anywhere.
How towers of hanoi works
Move n disks from peg A to peg C, one at a time, never placing a bigger disk on a smaller one. The trick is to stop thinking about individual moves. Assume you can already move n−1 disks - then the answer is three lines: shift n−1 aside onto the spare, move disk n, shift n−1 back on top.
That assumption is the entire skill of recursion. hanoi(4) does not know how to move anything; it delegates two hanoi(3) problems and performs exactly one real move itself. The call stack holds the plan - by the time the first disk actually moves, three frames of pending intent sit above it.
The recurrence T(n) = 2·T(n−1) + 1 solves to 2ⁿ − 1 moves - 15 for four disks, 255 for eight - and no algorithm can do fewer, because the biggest disk cannot move until the whole n−1 tower is off it and must be rebuilt on top afterwards. Unlike naive Fibonacci, nothing here is wasted: the answer itself is exponentially long.
Step by step
- Three disks sit on peg A. hanoi(3, A→C) cannot touch disk 3 yet, so it first delegates hanoi(2, A→B).
- That delegates again: hanoi(1, A→C) moves disk 1 straight to C. Move 1, with three frames on the call stack.
- Disk 2 is clear now and crosses A→B for move 2; disk 1 rejoins it with C→B, move 3. The two-disk tower is parked on the spare.
- The move everything else exists for: disk 3 crosses A→C. Move 4 - the only time the largest disk ever moves.
- hanoi(2, B→C) rebuilds on top: disk 1 to A, disk 2 to C, disk 1 to C - moves 5, 6 and 7.
- Seven moves, exactly 2³ − 1. The stack has fully unwound, and both sub-towers were solved by the same three-line plan.
Complexity
| Worst case time | O(2ⁿ) |
|---|---|
| Space | O(n) |
T(n) = 2·T(n−1) + 1, which solves to 2ⁿ − 1 - and that is optimal.
Reference implementation
Python
def hanoi(n, src="A", dst="C", spare="B"):
if n == 0:
return
hanoi(n - 1, src, spare, dst) # clear the way
print(f"move disk {n}: {src} -> {dst}")
hanoi(n - 1, spare, dst, src) # rebuild on top
# Total moves: 2^n - 1, and that is provably optimal.JavaScript
function hanoi(n, src = "A", dst = "C", spare = "B", moves = []) {
if (n === 0) return moves;
hanoi(n - 1, src, spare, dst, moves);
moves.push([n, src, dst]);
hanoi(n - 1, spare, dst, src, moves);
return moves; // length is 2^n - 1
}Worth noticing
The recursion writes itself once you accept the assumption
Assume you can already move n−1 disks. Then moving n is three lines: shift n−1 aside, move the big one, shift n−1 back. Believing the smaller case is exactly what makes recursion work - and what makes it hard to learn.
2ⁿ − 1 moves, and no fewer
T(n) = 2·T(n−1) + 1 with T(0) = 0 solves to 2ⁿ − 1. The largest disk must move at least once, and clearing the way for it requires solving the whole n−1 problem twice - so this is optimal, not just what this algorithm happens to do.
Exponential without any wasted work
Unlike naive fib, nothing is recomputed here. The output itself is exponentially long - 8 disks genuinely require 255 moves. Some problems are exponential in the answer, not in the method.
Common pitfalls
- Scrambling the peg arguments. The two recursive calls rotate the roles differently - (from, spare, to) going down, (spare, to, from) coming back - and swapping one pair quietly stacks big disks on small ones.
- Recursing without the n == 0 stop. This variant bottoms out at zero disks and does nothing there; forget that guard and the recursion never reaches a real move.
- Trying to track disk positions yourself. The state lives in the call stack's pending frames - trust the sub-solution and the bookkeeping disappears.
- Running it at scale. The output is the cost: 20 disks is over a million moves, and 64 - the original legend - runs 585 billion years at one move per second.
Where it is used
- The canonical recursion exercise: three lines that force you to trust the smaller case.
- Interview recurrences: deriving T(n) = 2·T(n−1) + 1 and solving it is the standard warm-up for cost analysis.
- Backup rotation: the Tower of Hanoi scheme cycles media so recent restore points stay dense and older ones sparse.
- A lower bound you can actually prove: some problems are exponential because their answer is, not because the method is wasteful.
Frequently asked questions
What is the time and space complexity of Towers of Hanoi?
The worst case is O(2ⁿ) time: the recurrence T(n) = 2·T(n−1) + 1 solves to exactly 2ⁿ − 1 moves, so 4 disks take 15 and 8 take 255. Space is O(n) for the recursion depth - only n frames are ever live at once, even though the move count is exponential.
Why is 2ⁿ − 1 the minimum number of moves?
The largest disk must move at least once, and before it can, all n−1 smaller disks must be stacked on the spare peg - a full (n−1)-disk problem. Afterwards they must be rebuilt on top of it - another full one. So any solution costs at least twice the (n−1) minimum plus one, which is the recurrence this algorithm achieves exactly.
How long would the legendary 64 disks take?
2⁶⁴ − 1 is about 18 quintillion moves. At one move per second that is roughly 585 billion years - around 42 times the age of the universe. The original legend has the world ending when the monks finish, and the arithmetic says nobody needs to worry.
Would memoisation speed up Towers of Hanoi?
No. Memoisation removes repeated work, and Hanoi has none - every one of its 2ⁿ − 1 moves is distinct output, not recomputation. An algorithm cannot emit an exponentially long answer in less than exponential time. Contrast naive Fibonacci, which is exponential purely through waste.