Algorithm

Tower of Hanoi

Recursion Pattern

Tower of Hanoi

There are three pegs and n disks of different sizes stacked on the first peg, largest at the bottom. Move the whole stack to the third peg. You may move only one disk at a time, only the top disk of a peg, and you may never place a larger disk on top of a smaller one. Return (or print) the sequence of moves; the minimum number of moves is 2ⁿ − 1. This is the classic showcase of multiple recursion.

CONSTRAINTS
  • 1 <= n <= 5 (kept small: the move count is 2ⁿ − 1)
  • Exactly 3 pegs, usually named source, auxiliary, destination
  • A larger disk may never rest on a smaller one
EXAMPLE 1
Input: n = 1
Output: 1 move
Move the single disk straight from source to destination. 2¹ − 1 = 1.
EXAMPLE 2
Input: n = 2
Output: 3 moves
Small disk to the spare peg, large disk to destination, small disk onto destination. 2² − 1 = 3.
EXAMPLE 3
Input: n = 3
Output: 7 moves
Solve 2 disks onto the spare (3 moves), move the largest (1 move), solve 2 disks onto destination (3 moves). 3 + 1 + 3 = 7 = 2³ − 1.
EXAMPLE 4
Input: n = 4
Output: 15 moves
Each added disk roughly doubles the work: 2⁴ − 1 = 15.
What is the minimum number of moves?
Exactly 2ⁿ − 1. The recurrence moves(n) = 2·moves(n−1) + 1 with moves(0) = 0 solves to 2ⁿ − 1, and this is provably optimal — you cannot do better.
Can I memoize it like Fibonacci?
No. Fibonacci's two calls overlap on the same inputs, so caching helps. Hanoi's two calls solve disjoint sub-tasks that never repeat, so there is nothing to cache — the 2ⁿ − 1 moves are all genuinely necessary.
How deep does the recursion go?
At most n frames at any instant, even though it produces exponentially many moves. Stack depth is O(n); total moves are O(2ⁿ). The two are different quantities.
How do the peg roles change between the two recursive calls?
The spare peg swaps. In step 1 the destination acts as the spare; in step 3 the source acts as the spare. Relabeling the three pegs correctly per call is the only bookkeeping the problem requires.

Tower of Hanoi seems to demand clever planning — how do you juggle n disks across three pegs without ever stacking big on small? Recursion dissolves the cleverness. The key is to stop thinking about individual disk moves and instead trust a smaller version of the very same task. This problem showcases multiple recursion: two recursive calls that are not overlapping subproblems (so no memoization) but genuinely different sub-tasks.

The reframe: to move n, first move n − 1

To move n disks from the source peg to the destination peg, the only real obstacle is the biggest disk at the bottom — it can only go to the destination when the destination is empty and all n − 1 disks above it are parked somewhere out of the way. That "somewhere" is the third (auxiliary) peg. So the entire task splits into three steps:

1. Move the top n − 1 disks from source to auxiliary (a smaller Hanoi problem, using destination as the spare peg).
2. Move the single largest disk from source directly to destination.
3. Move those n − 1 disks from auxiliary onto destination (another smaller Hanoi problem, using source as the spare).

Steps 1 and 3 are the same problem with one fewer disk — just with the peg roles relabeled. That is the leap of faith: assume you can already solve Hanoi for n − 1 disks, and the n-disk solution is these three lines.

python
def hanoi(n, source, dest, aux):
    if n == 0:                       # base case: no disks, nothing to do
        return
    hanoi(n - 1, source, aux, dest)  # 1: park n-1 on the spare peg
    move(source, dest)               # 2: move the largest disk
    hanoi(n - 1, aux, dest, source)  # 3: bring n-1 onto the destination
Why two calls, and why it is not Fibonacci

This is multiple recursion — two recursive calls per invocation, like Fibonacci. But there is a crucial difference: Fibonacci's two calls overlapped (both branches needed fib(k)), which is why caching helped. Hanoi's two calls solve disjoint sub-tasks — moving a specific set of disks between a specific pair of pegs — so nothing repeats and there is nothing to memoize. The work is genuinely 2ⁿ − 1 moves; that is the true minimum, not wasted recomputation. Counting the calls: each level doubles the number of sub-tasks, giving O(2ⁿ) total moves and O(n) stack depth (the recursion is at most n frames deep at any instant, even though it makes exponentially many moves overall).

Worked Example:hanoi(2, A, C, B) — move 2 disks from A to C
- hanoi(2, A→C, spare B): first move 1 disk A→B.
- hanoi(1, A→B, spare C): move 1 disk A→B → move disk1: A → B.
- Move the big disk: move disk2: A → C.
- Then move 1 disk B→C.
- hanoi(1, B→C, spare A): move disk1: B → C.
- Total: 3 moves (2² − 1 = 3), and no rule is ever violated because the small disk is always parked before the big one moves.
Key Insightrecursion lets you specify what a correct move sequence looks like — "clear the way, move the big one, rebuild on top" — without ever tracking the global state of all three pegs in your head. You describe one level honestly and trust the smaller calls for the rest. That is the entire power of recursive decomposition.
The takeaway

Hanoi is the archetype for problems solved by describing the step, not the whole plan: define the task in terms of smaller instances of itself, handle the single pivotal action in the middle, and let recursion assemble the exponentially many moves. The same "do the sub-task, take one action, do the mirror sub-task" shape reappears across recursion and backtracking — generating permutations, exploring decision trees, solving puzzles. When a problem's full plan looks impossibly tangled, ask what one smaller version you could trust, and what single action connects two of them.

O(2ⁿ) Time (2ⁿ − 1 moves) · O(n) Stack Multiple Recursion