The Tower of Hanoi is the cleanest puzzle in all of recursion: move a stack of disks from one peg to another, never resting a bigger disk on a smaller one, using a third peg as scratch space. The whole solution is three lines once you trust recursion to handle the smaller piles for you.
Core idea. To move n disks from src to dst using aux: first move the top n-1 disks out of
the way onto aux, then move the single biggest disk straight to dst, then move those n-1 disks
from aux on top of it. The two sub-problems are smaller copies of the same task. For n = 3 this takes
2^3 - 1 = 7 moves.
The rules are simple: move one disk at a time, only the top disk of a peg, and never place a larger disk on a smaller one. With 3 disks starting on peg A, the goal is to rebuild the tower on peg C.
Intuition
The trick is to not think about all the disks at once. Pretend you already know how to move a stack of n-1 disks anywhere you like. Then moving n disks is almost trivial: shove the top n-1 onto the spare peg (you "know how"), carry the one remaining giant disk to its home, and drop the n-1 back on top.
That leap of faith is the recursion. The function calls itself on the smaller n-1 pile twice, and the only real work it does itself is moving exactly one disk. The base case is an empty pile (n = 0): there is nothing to move, so it just returns. Every legal move you see in the animation is one of these single-disk moves, bubbling up from deep inside the recursion.
Walk through it
Step through the animation on the right. Disks are drawn by width: disk 1 is narrowest, disk 3 is widest. They start stacked on peg A and must end stacked on peg C. The move marker rides above whichever disk just moved.
The 7 moves come out in this exact order: disk 1 goes A → C, disk 2 goes A → B, disk 1 hops C → B (now the two small disks are parked on B), then the big disk 3 slides straight A → C. The second half mirrors the first: disk 1 goes B → A, disk 2 goes B → C onto disk 3, and finally disk 1 lands A → C to cap the tower. Notice how disk 1 moves on every odd step and the whole left half just clears a runway for the single move of disk 3 in the middle.
The code, line by line
def hanoi(n, src, dst, aux):
if n == 0:
return
hanoi(n - 1, src, aux, dst)
print(f"move disk {n}: {src} -> {dst}")
hanoi(n - 1, aux, dst, src)- Line 2 is the base case: with zero disks there is nothing to do, so the recursion bottoms out and unwinds.
- Line 4 is the first recursive call: move the top
n-1disks offsrcontoaux, treatingdstas the temporary peg. This clears the way for the big disk. - Line 5 is the single real move: the one disk that this call is personally responsible for slides from
srctodst. This is the line each animation step highlights. - Line 6 is the second recursive call: move that
n-1pile fromauxontodst, now usingsrcas the temporary peg, finishing the tower. - The roles of
dstandauxswap between the two recursive calls — that swap is the entire secret of the puzzle.
Complexity
| Case | Time | Notes |
|---|---|---|
| Time | O(2^n) (slow) | moves obey T(n) = 2T(n-1) + 1 = 2^n - 1 |
| Space | O(n) (moderate) | recursion depth is n call frames on the stack |
O(n) (moderate)Each call spawns two calls one size smaller plus a single move, so the move count doubles with every extra disk: T(n) = 2T(n-1) + 1, which solves to 2^n - 1. That growth is unavoidable — 2^n - 1 is provably the minimum number of moves. The space is only O(n) because at any instant the call stack is just one path down the recursion, at most n frames deep.
When to use / pitfalls
Tower of Hanoi is the canonical example for explaining recursion and recurrence relations. If an
interviewer asks you to count moves, derive 2^n - 1 from T(n) = 2T(n-1) + 1. If they ask for the
sequence of moves, the three-line recursion is the whole answer — and the key insight to verbalize is
that dst and aux trade places between the two recursive calls.
The most common bug is passing the pegs in the wrong order to the recursive calls. The first call
must use the real destination as its scratch peg (aux and dst swap), and the second must use the
original source as scratch. Get that swap backwards and disks land on the wrong peg or you break the
no-bigger-on-smaller rule. Also remember the base case is n == 0 (or n == 1 with a direct move) — an
off-by-one there causes infinite recursion.
Practice
For 3 disks starting on A, what is the very first disk that moves, and where does it go?
1. How many moves are needed to solve Tower of Hanoi with 3 disks?
2. What does the function do in its base case?
3. Between the two recursive calls, what changes in their arguments?
4. Why is the time complexity O(2^n)?