Tower of Hanoi in Python — The Recursion That Doubles

Last update: June 2026. All opinions are my own.

All opinions are my own.

Why this puzzle keeps me coming back

The Tower of Hanoi is the kind of problem that looks trivial at three disks, feels manageable at five, and turns into a wall at eight. The number of moves doubles every time you add a disk — from 7 moves to 15 to 31 — but the recursive Python solution doesn't get any longer.

This post walks through the standard recursive solution, why it works, and the iterative pattern that lets you solve any size puzzle by hand without backtracking. selfboot

If you want to play it interactively, there's a working version on this site at the bottom of Beyond Work.

The puzzle, in one paragraph

Three rods (let's call them A, B, C) and n disks of different sizes stacked in ascending order on rod A — the smallest on top, the largest on the bottom. The goal is to move all n disks to rod C following three rules:

1. Only one disk moves at a time.
2. A move means taking the top disk off one rod and placing it on another rod (or an empty rod).
3. A disk may never sit on top of a smaller one.

The middle rod B is the spare — sometimes called the auxiliary.

The recursive solution in 8 lines of Python

def tower_of_hanoi(n, source, auxiliary, target):
    if n == 1:
        print(f"Move disk 1 from {source} to {target}")
        return
    tower_of_hanoi(n - 1, source, target, auxiliary)
    print(f"Move disk {n} from {source} to {target}")
    tower_of_hanoi(n - 1, auxiliary, source, target)

Run it on three disks:

print("Solving Tower of Hanoi for 3 disks:")
tower_of_hanoi(3, "A", "B", "C")

Solving Tower of Hanoi for 3 disks:
Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Seven moves. That's the minimum for 3 disks.

Why it works: the recursive insight

The recursion captures the mental trick behind solving the puzzle by hand. To move n disks from source to target using auxiliary as a spare, you do three things:

1. Move n−1 disks from source to auxiliary. Use target as the temporary spare.
2. Move the largest disk (the n-th one) from source straight to target.
3. Move the n−1 disks from auxiliary onto target. Use source as the temporary spare.

The trick is that steps 1 and 3 are the same problem with one fewer disk. The recursion delegates them to a smaller version of itself.

At the smallest case, n == 1, the function stops recursing and just prints the single move. Everything above that is a chain of these three-step operations folding back through the call stack.

The arguments swap — the only thing that can break

Look closely at the three function calls:

tower_of_hanoi(n - 1, source, target, auxiliary)   # use target as spare
print(f"Move disk {n} from {source} to {target}")  # the big move
tower_of_hanoi(n - 1, auxiliary, source, target)   # use source as spare

In the recursive calls, the roles of the rods swap. In step 1, target plays the role of the spare; in step 3, source does. Getting that swap right is the only place this code can break — and it's the bit that confuses everyone the first time they read recursion.

The maths: 2ⁿ − 1 moves

For n disks, the minimum number of moves is exactly:

T(n) = 2 × T(n − 1) + 1 with T(1) = 1

Solving this recurrence gives:

T(n) = 2ⁿ − 1

The 64-disk version is the original legend: a temple where monks move 64 golden disks one at a time. Even at one move per second, finishing the puzzle would take about 585 billion years — long after the universe has ended.

Useful side fact: the biggest disk always moves exactly in the middle of the optimal sequence. For 3 disks (7 moves) it moves on turn 4. For 4 disks (15 moves), turn 8. For 6 disks (63 moves), turn 32. For 8 disks (255 moves), turn 128. If you hit a halfway point and the biggest disk hasn't moved, you've taken a detour.

How to actually play it by hand — the three hints

The recursive solution is elegant, but it's not how you solve the puzzle by hand. There's an iterative pattern based on disk parity that lets a human play optimally without ever having to think recursively. It's three small rules:

Hint 1 — Every other turn

The smallest disk moves every other turn. The moves in between are forced.

This means literally alternating: disk 1 moves on turn 1, then a different disk on turn 2, disk 1 on turn 3, different on turn 4, and so on forever. Odd-numbered moves are disk 1; even-numbered moves are something else.

The "forced" move sounds harder than it is. After disk 1 has moved, look at the other two towers (ignore the one disk 1 is sitting on). Between those two, there are only two possible disk moves — and one of them would put a larger disk on a smaller one, which is illegal. The other one is the only legal move. That's the forced move.

Hint 2 — Which direction disk 1 cycles

Odd total disks → disk 1 starts toward the target. Even total disks → disk 1 starts toward the spare. After the first move, disk 1 always cycles in the same direction.

Once you know the direction, every disk-1 move is determined. Read it like a clock: A then B then C then A again, in whichever rotation matches your parity. Don't think left/right — think next station in the cycle.

Hint 3 — The big plan

To move N disks from source to target, first move N−1 disks onto the spare. Then move the biggest disk. Then move N−1 disks back on top.

This is Hint 3, and it's just the recursive structure stated again. It's not really a tactical move-by-move hint — it's the strategic checkpoint that tells you whether you're on track.

For 8 disks: the big checkpoint is when all of disks 1–7 are parked on B, with disk 8 alone on A. From there, one move puts disk 8 on C, and the rest of the puzzle is a 7-disk problem from B to C.

If you ever lose track of where you are, recognise the checkpoint structure: "I'm trying to free disk N. For that, all smaller disks need to be off the way."

Why even puzzles start differently

The reason odd and even puzzles start in opposite directions is hidden inside the recursive structure.

The first big goal of any puzzle is always to free the biggest disk (disk N). For that, the N−1 disks above it must be stacked on the spare tower (B).

That hidden subproblem — "move N−1 disks from A to B" — is itself a smaller Tower of Hanoi. And its parity is one less than the parent puzzle's. So:

• 8 disks (even): the hidden subproblem is 7 disks from A to B. A 7-disk problem is odd, and an odd puzzle's disk 1 starts toward its target. The target of that subproblem is B. So disk 1 first goes to B.
• 7 disks (odd): the hidden subproblem is 6 disks from A to B. A 6-disk problem is even. An even puzzle's disk 1 starts toward its spare. The spare of that subproblem is C (the spare of the outer problem). So disk 1 first goes to C.

That's why the rule flips with parity. It's not a coincidence — it's the recursion poking through.

A common confusion: "where does disk 1 go next?"

The most common stumbling block I see learners hit: they pick disk 1's destination from the position of the larger disks. They look at the board and think "this disk would land on an even-numbered disk — is that good or bad?"

Honestly: that pattern is real, but it's a side effect, not the steering rule. The reliable rule is always the cycle from Hint 2. If disk 1 is currently on B in an even puzzle, the next station is C — not because C is "magic", but because B → C is the next step in the fixed clock-cycle.

The decision checklist while playing

Distilled to a checklist you can run in your head:

1. Is this an odd-numbered move? → Move disk 1.
2. Is this an even-numbered move? → Move a disk that is NOT disk 1.
3. If moving disk 1, where? → Use the cycle from Hint 2.
4. If not moving disk 1, what? → Ignore the tower disk 1 is on. Between the other two, make the only legal move.
5. Am I lost? → Look for the checkpoint: smaller stack parked away, biggest disk free, smaller stack ready to return.

The simplest summary: Hint 1 tells you WHO moves, Hint 2 tells you WHERE disk 1 goes, Hint 3 tells you WHY the whole thing is working.

Closing thought

Recursion is the kind of pattern that looks magical the first time and obvious the tenth. Tower of Hanoi is a clean example because the recursive structure of the algorithm mirrors the recursive structure of the puzzle — each subproblem is a smaller copy of the original.

The other thing I like about it: the eight lines of Python work for n = 3 and n = 64 exactly the same way. The compiler doesn't know or care that one finishes instantly and the other outlives the universe.

The full notebook is on Google Colab. The interactive version lives at the bottom of Beyond Work — and if you get stuck, the hints in the sidebar walk you through Hints 1, 2, and 3 in the same order as this post.