A-Level · Recursion

Towers of Hanoi

Three pegs. A stack of disks on the first peg, largest at the bottom. Move the entire stack to the third peg, one disk at a time, never placing a larger disk on a smaller one. That's the whole puzzle. What makes it worth studying is that the only sane way to solve it is to trust recursion completely, even when it feels like cheating.

Section 2

Try it yourself first

Click a peg to pick up its top disk, click another peg to drop it there. Illegal moves are simply refused. Get all disks onto peg C to win.

Click peg A to pick up the top disk.

Disks

Controls

Moves: 0

Section 3

The insight: don't think about all the disks at once

Trying to plan every single move in advance is exactly why this puzzle feels impossible. The recursive solution refuses to do that. It only ever thinks about the biggest disk.

To move n disks from a source peg to a destination peg, using a spare peg to help:

  1. Move the top n-1 disks from source to spare (using destination as the helper this time)
  2. Move the single remaining, biggest disk directly from source to destination
  3. Move those n-1 disks from spare to destination (using source as the helper this time)

Steps 1 and 3 are exactly the same kind of problem as the original, just with one fewer disk. That's the whole trick: you never need to know how to move n-1 disks, you just trust that the same three-step recipe handles it, all the way down to a single disk, which is trivial to move directly.

Section 4

Watch the algorithm actually solve it

Every move below comes from the exact recursive recipe above, nothing hardcoded. Step through and watch the pattern: it obsessively clears disks out of the way, moves one big disk, then puts them back.

Ready. This will solve a 3-disk tower using the recursive method.

Number of disks

Controls

Move 0 of 0

Section 5

The recursive call tree, for 3 disks

Each box is one call to the recursive procedure. Notice it branches, just like Fibonacci, but here there's no repeated work, every branch handles a genuinely different sub-problem, which is exactly why memoisation has nothing to offer this algorithm.

Ready. Press Step to build the call tree for moving 3 disks from A to C.

Controls

Exam tips

  • Every leaf in this tree is a call moving exactly 1 disk, the base case, directly, no further recursion.
  • Unlike Fibonacci, no sub-problem here ever repeats. hanoi(2, A→B) and hanoi(2, B→C) are moving different disks between different pegs, genuinely distinct work, not duplicated effort.
Section 6

Why the move count is exactly 2ⁿ - 1

Each call to move n disks makes exactly two recursive calls to move n-1 disks, plus one move of its own. That single sentence is enough to derive the whole formula.

Let T(n) = number of moves needed for n disks.
T(n) = T(n-1) + 1 + T(n-1) = 2×T(n-1) + 1
T(1) = 1 (just move the one disk)

T(2) = 2×1 + 1 = 3
T(3) = 2×3 + 1 = 7
T(4) = 2×7 + 1 = 15
T(n) = 2n - 1

Try a disk count

Exam tips

  • T(n) = 2T(n-1) + 1 is itself a recurrence relation, exactly the kind of thing you're expected to both write down and solve at this level.
  • This is genuinely exponential growth: 64 disks (the original legend's version) would take 2⁶⁴ - 1 moves, over 18 quintillion, which at one move per second would still be running long after the sun has become a red giant.
Section 7

Check your understanding