Tower of Hanoi- Recursion Explained with Examples

What Is the Tower of Hanoi?

The Tower of Hanoi is a classic puzzle with three pegs and N disks stacked on one peg. The goal is simple: move the entire stack to another peg, following two rules.

It sounds easy. It's not. The puzzle was invented by French mathematician Édouard Lucas in 1883, and it's become the go-to example for teaching recursion in computer science.

Here's why: the solution requires you to solve the exact same problem, just smaller. That's recursion.

The Rules You Must Follow

Move one disk at a time
Never place a larger disk on top of a smaller one
You can only move the top disk from any peg

That's it. No tricks, no loopholes.

Why Recursion Fits Perfectly

Recursion works when a problem can be broken into identical subproblems. Tower of Hanoi is built for this.

To move N disks from source to destination:

Move N-1 disks from source to temporary peg
Move the largest disk from source to destination
Move N-1 disks from temporary to destination

Steps 1 and 3 are the same problem—just smaller. That's the recursive call.

The Base Case

Every recursive solution needs a stopping point. For Tower of Hanoi, that's N = 1. One disk? Just move it. No recursion needed.

Step-by-Step: 3 Disks

Let's walk through moving 3 disks from peg A to peg C.

Move 1

Move disk 1 from A to C

Move 2

Move disk 2 from A to B

Move 3

Move disk 1 from C to B

Move 4

Move disk 3 from A to C

Move 5

Move disk 1 from B to A

Move 6

Move disk 2 from B to C

Move 7

Move disk 1 from A to C

Total moves: 7

Notice the pattern? The solution follows a predictable sequence. You don't need to figure it out manually—the recursion handles it.

The Formula

Minimum moves for N disks:

Moves = 2ⁿ - 1

So:

1 disk = 1 move
2 disks = 3 moves
3 disks = 7 moves
4 disks = 15 moves
10 disks = 1,023 moves

The numbers grow fast. This is exponential time complexity.

Code Implementation

Python


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

# Example
tower_of_hanoi(3, 'A', 'C', 'B')

JavaScript


function towerOfHanoi(n, source, destination, auxiliary) {
    if (n === 1) {
        console.log(`Move disk 1 from ${source} to ${destination}`);
        return;
    }
    
    towerOfHanoi(n - 1, source, auxiliary, destination);
    console.log(`Move disk ${n} from ${source} to ${destination}`);
    towerOfHanoi(n - 1, auxiliary, destination, source);
}

towerOfHanoi(3, 'A', 'C', 'B');

The code is almost identical in both languages. That's the power of understanding the algorithm—you're not tied to syntax.

Complexity Analysis

Aspect	Complexity	Explanation
Time	O(2ⁿ)	Each disk doubles the work
Space	O(n)	Recursive call stack depth
Moves	2ⁿ - 1	Minimum possible moves

You can't optimize the time complexity. The puzzle requires 2ⁿ - 1 moves. That's mathematically proven.

Getting Started: Build Your Own Solver

Want to implement this yourself? Here's the process:

Define the base case — when N = 1, just print the move
Break the problem — move N-1 disks to the auxiliary peg
Move the bottom disk — from source to destination
Stack the rest — move N-1 from auxiliary to destination

That's the entire algorithm. Four steps.

Common Mistakes

Forgetting the base case — your recursion will never stop
Swapping pegs incorrectly — check your argument order in recursive calls
Overcomplicating it — the recursive solution is short. If your code is long, something's wrong

Where You'll See This

Tower of Hanoi isn't just academic. It shows up in:

Algorithm courses — recursion fundamentals
Interview questions — testing recursive thinking
Puzzle games — the actual game mechanics
Mathematical proofs — induction examples

Understanding this problem means you understand one of the cleanest examples of recursion you'll encounter.

The Bottom Line

Tower of Hanoi demonstrates recursion perfectly: a complex problem solved by breaking it into identical smaller problems. The algorithm is straightforward—move N-1, move the biggest, move N-1 back.

Master this, and recursion stops feeling abstract. It becomes intuitive.