Tower of Hanoi - Algorithm Tutorial

Introduction

The Tower of Hanoi is one of the most famous problems in computer science, invented by French mathematician Édouard Lucas in 1883.

The puzzle demonstrates the power of recursion: solving a problem by breaking it into smaller instances of the same problem.

Legend: According to myth, monks in a temple are moving 64 golden disks between three diamond pegs. When they finish, the world will end. At one move per second, this would take about 585 billion years!

Why it matters:

Foundation for understanding recursive algorithms
Appears in technical interviews
Models real-world problems (backup strategies, memory management)

The Key Insight

To move $n$ disks from A to C, you cannot move the largest disk until all other disks are out of the way.

The insight: To move $n$ disks from source to destination:

First, move the top $n-1$ disks somewhere else (to the auxiliary peg)
Then move the largest disk directly to the destination
Finally, move the $n-1$ disks from auxiliary to destination

This is a recursive structure. Step 1 and step 3 are the same problem with fewer disks!

Why does this work?

The largest disk doesn't interfere with smaller disks (rule 3)
Once smaller disks are moved away, the largest can go directly to destination
The auxiliary peg "holds" the smaller disks temporarily

Recursive Algorithm

The algorithm follows directly from the insight:

text

function hanoi(n, source, auxiliary, destination):
    if n == 1:
        print source + destination
        return

    // Step 1: Move n-1 disks from source to auxiliary
    hanoi(n - 1, source, destination, auxiliary)

    // Step 2: Move largest disk from source to destination
    print source + destination

    // Step 3: Move n-1 disks from auxiliary to destination
    hanoi(n - 1, auxiliary, source, destination)

Notice how the pegs swap roles in recursive calls:

In step 1: destination becomes auxiliary, auxiliary becomes destination
In step 3: auxiliary becomes source, source becomes auxiliary

This "role swapping" makes the algorithm work correctly.

Complexity Analysis

Time Complexity: $O(2^n)$

Let $T(n)$ = number of moves for $n$ disks.

Recurrence: $T(n) = 2 \cdot T(n-1) + 1$

Base case: $T(1) = 1$

Solving: $T(n) = 2^n - 1$

This is optimal. It is mathematically proven that you cannot solve the puzzle in fewer than $2^n - 1$ moves.

Space Complexity: $O(n)$

The recursion depth is $n$ (one level per disk size), so the call stack uses $O(n)$ space.

Growth rate:

$n$	Moves
5	31
10	1,023
15	32,767
20	1,048,575

1. Trust the recursion

Don't try to trace every recursive call. Trust that if the base case and recursive step are correct, the algorithm works.

2. Identify the subproblem

The key to recursion is recognizing that a smaller version of the same problem exists. Here: moving $n$ disks reduces to moving $n-1$ disks.

3. Handle parameter changes carefully

Notice how source, auxiliary, and destination swap roles in recursive calls. This is a common pattern in recursive algorithms.

4. The formula $2^n - 1$

This exponential growth appears frequently in CS:

Binary tree traversals
Subset enumeration
Divide-and-conquer algorithms

Extensions to explore:

What if you can only move between adjacent pegs?
What if there are 4 pegs? (Frame-Stewart algorithm)
Can you find the k-th move without computing all moves?

Tower of Hanoi Algorithm Tutorial

Introduction

The Key Insight

Recursive Algorithm

Complexity Analysis

Implement this Algorithm

Related Algorithms

Key Takeaways