Problem Statement

Tower of Hanoi

Picture three pegs in the ground and a stack of donut-shaped disks slid onto the first peg, biggest at the bottom and smallest at the top. Your job is to move the whole stack to the third peg. The rules: you can move only one disk at a time, you only ever lift the top disk off a peg, and you can never set a bigger disk on top of a smaller one. The middle peg is just a parking spot to help you. The key tool here is recursion, which means a function that solves a problem by calling itself on a smaller version of the same problem. That fits perfectly, because moving a tall stack turns out to be the same job as moving a shorter stack, just done a few times. The smallest number of moves needed is 2^n - 1, where n is the number of disks.

mediumRecursionBacktrackingTime: O(2^n) · Space: O(n)

Signals to notice

move n disks between pegscan't place larger on smallerclassic recursion

Brute force first

Not applicable — recursion IS the solution. Minimum moves = 2^n - 1.

The key insight

Move n-1 disks to auxiliary. Move largest to target. Move n-1 from auxiliary to target. T(n) = 2T(n-1) + 1 = 2^n - 1.

Trace it on `n=3, source='A', destination='C', auxiliary='B'`

hanoi(3,A,C,B): n!=1 -> recurse hanoi(2,A,B,C) to clear disks 1-2 onto B
  hanoi(2,A,B,C): recurse hanoi(1,A,C,B) -> emit 'Move disk 1 from A to C'
  hanoi(2,A,B,C): emit 'Move disk 2 from A to B', then recurse hanoi(1,C,B,A) -> emit 'Move disk 1 from C to B'
hanoi(3,A,C,B): emit 'Move disk 3 from A to C' (bottom disk to target)
hanoi(3,A,C,B): recurse hanoi(2,B,C,A) to restack disks 1-2 onto C
  hanoi(2,B,C,A): recurse hanoi(1,B,A,C) -> emit 'Move disk 1 from B to A'
  hanoi(2,B,C,A): emit 'Move disk 2 from B to C', then recurse hanoi(1,A,C,B) -> emit 'Move disk 1 from A to C'
Done: 7 moves printed = 2^3 - 1

What must stay true

To expose the bottom disk, all n-1 above must be elsewhere. This creates two identical subproblems of size n-1 plus one direct move.

Shape of the loop

function hanoi(n, src, dst, aux):
    if n == 1: emit("move disk 1 from", src, "to", dst); return
    hanoi(n-1, src, aux, dst)        # clear n-1 off onto aux
    emit("move disk", n, "from", src, "to", dst)  # move bottom disk
    hanoi(n-1, aux, dst, src)        # restack n-1 onto dst

Pseudocode only — the full worked solution lives in the Solution tab.

Easy way to go wrong

Trying iterative without understanding the recursion — while iterative solutions exist, the recursive decomposition is the natural insight.

Backtracking Pattern