Tower of Hanoi —
Move n-1 out of the way, move the big one, move n-1 back.
Move a stack of disks from one peg to another, never placing a larger disk on a smaller one, using a spare peg — the classic problem that makes recursive thinking click for a lot of people. Watch the 3-disk solve unfold on LearnBug in exactly 7 moves, and see why it's always 2ⁿ−1.
What is Tower of Hanoi?
Three pegs, n disks stacked largest-to-smallest on the first peg. Move the whole stack to the third peg, one disk at a time, never placing a larger disk on a smaller one. The recursive insight: to move n disks, move the top n-1 disks out of the way, move the biggest disk directly, then move those n-1 disks on top of it.
Why visualization helps
The recursive call hanoi(n-1, source, target, aux) before the move, and hanoi(n-1, aux, source, target) after it, use the exact same three peg names in a different order each time — which is genuinely hard to track by reading code alone. LearnBug shows which peg is "source," "auxiliary," and "target" at every recursive call, so the role-swapping is visible instead of something you have to trust.
Three steps, applied at every size
1. Move n-1 disks out of the way
Move the top n-1 disks from source to the auxiliary peg — treating this as its own smaller Tower of Hanoi problem, solved recursively.
2. Move the biggest disk directly
With the source peg down to just the largest disk, move it straight to the target peg — this is the one actual move at this recursion level, not another recursive call.
3. Move n-1 back on top
Move those n-1 disks from the auxiliary peg onto the target peg, on top of the disk that's already there — another recursive call, roles swapped.
hanoi(3, A, B, C) — move 3 disks from peg A to peg C
hanoi(3, A, B, C) needs hanoi(2, A, C, B) first — move the top 2 disks out of the way, to B
Before disk 3 (the biggest) can move, disks 1 and 2 need to be off peg A entirely. That's a smaller Tower of Hanoi: move 2 disks from A to B, using C as the spare.
Move disk 3 — the biggest — directly from A to C
This is the ONE real move at the top level of recursion. Peg A now has nothing left on it, peg B holds disks 1 and 2, and disk 3 sits alone on peg C.
hanoi(2, B, A, C) — move disks 1 and 2 from B onto C, on top of disk 3
Same pattern as step 1, but with the peg roles swapped: now B is the source, A is the spare, C is the target that already holds disk 3.
All 3 disks now sit on peg C, largest to smallest — done in 7 moves
3 moves to clear the way, 1 move for the biggest disk, 3 moves to rebuild the stack — 3 + 1 + 3 = 7, matching 2³ − 1 exactly.
Return: 7 moves total ✓ 2ⁿ−1 for n=3
Recursive Tower of Hanoi
def hanoi(n, source, aux, target):
if n == 1:
print(f"Move disk 1 from {source} to {target}")
return
hanoi(n - 1, source, target, aux) # 1. clear n-1 disks out of the way
print(f"Move disk {n} from {source} to {target}") # 2. move the big one
hanoi(n - 1, aux, source, target) # 3. move n-1 back on top
hanoi(3, "A", "B", "C")Complexity Notes
Frequently asked questions
Why is it always exactly 2ⁿ − 1 moves?
Let T(n) be the number of moves for n disks. Moving n disks takes T(n-1) moves to clear the way, 1 move for the biggest disk, and T(n-1) moves to rebuild — so T(n) = 2·T(n-1) + 1, with T(1) = 1. Solving that recurrence gives T(n) = 2ⁿ − 1 exactly, and it's provably the minimum possible, not just what this particular algorithm happens to produce.
Why do the peg arguments swap order between the two recursive calls?
The first call moves n-1 disks from source to auxiliary, so auxiliary temporarily acts as the target and target acts as the spare — hence hanoi(n-1, source, target, aux). The second call moves those same n-1 disks from auxiliary onto the real target, with source now free to act as the spare — hence hanoi(n-1, aux, source, target). The peg names are the same three, just playing different roles each time.
Can Tower of Hanoi be solved iteratively?
Yes — there's a known iterative pattern (alternate moving the smallest disk in a fixed cyclic direction with one other legal move), but it's considerably less intuitive to derive or explain than the recursive version, which is why this problem is almost always taught recursively first.
What's the connection to binary numbers?
There's a neat one: the optimal move sequence for n disks corresponds exactly to counting from 1 to 2ⁿ−1 in binary and looking at which bit flips at each step — that bit position tells you which disk moves next. It's a nice example of how a combinatorial recursive structure often has a hidden closed-form pattern.
Watch every disk move — and every peg swap roles
Paste your Tower of Hanoi solution into LearnBug and see the recursion at every disk size.