Tower of Hanoi Explained for Beginners

If you’ve just started learning recursion, you’ve probably come across the Tower of Hanoi problem. At first glance, it looks confusing because the solution is almost entirely recursive. Once you understand the pattern, however, it becomes one of the easiest recursion problems to recognize.

Let’s break it down step by step.

What is the Tower of Hanoi?

Imagine three rods named:

• A (Source)
• B (Auxiliary/Temporary)
• C (Destination)

You have n disks of different sizes stacked on rod A. The largest disk is at the bottom, and the smallest is at the top.

Your goal is to move all the disks from rod A to rod C.

Rules

1. Move only one disk at a time.
2. Only the top disk of a rod can be moved.
3. A larger disk can never be placed on top of a smaller disk.

For example, with 3 disks:

The goal is to move all three disks to rod C while following the rules.

Understanding the Recursive Idea

Instead of trying to move all the disks at once, think about moving only the largest disk.

Can you move it immediately?

No.

All the smaller disks above it must be removed first.

So the problem naturally divides into three steps.

Step 1

Move the top n-1 disks from the source rod to the temporary rod.

Source  --->  Temporary

Step 2

Now the largest disk is free.

Move it from the source rod to the destination rod.

Source  --->  Destination

Step 3

Finally, move the n-1 disks from the temporary rod to the destination rod.

Temporary  --->  Destination

That’s the entire algorithm.

Notice something interesting?

Steps 1 and 3 are exactly the same problem, just with fewer disks.

That’s why recursion fits perfectly.

Visualizing with 3 Disks

We want to move:

A → C

First recursive call

Move 2 disks from A to B.

A -> B

Move the largest disk

Disk 3
A -> C

Second recursive call

Move the 2 disks from B to C.

B -> C

Eventually, recursion reaches just one disk, which is the simplest possible move.

Recursive Algorithm

TowerOfHanoi(n, source, destination, temporary)

if n == 0
    return

Move n-1 disks from source to temporary

Move nth disk from source to destination

Move n-1 disks from temporary to destination

Java Implementation

import java.util.Scanner;
public class TowerOfHanoi {
    static int steps = 0;
    public static void solveTowerOfHanoi(int disk,
                                         String src,
                                         String dest,
                                         String temp) {
        if (disk == 0)
            return;
        solveTowerOfHanoi(disk - 1, src, temp, dest);
        System.out.println("Move disk " + disk +
                " from " + src + " to " + dest);
        steps++;
        solveTowerOfHanoi(disk - 1, temp, dest, src);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int n = sc.nextInt();
        solveTowerOfHanoi(n, "A", "C", "B");
        System.out.println("Minimum steps = " + steps);
        sc.close();
    }
}

Dry Run for 2 Disks

Input

2

Execution

solve(2)

|
|-- solve(1)
|     |
|     |-- solve(0)
|     |
|     |-- Move disk 1 A → B
|     |
|     |-- solve(0)
|
|-- Move disk 2 A → C
|
|-- solve(1)
      |
      |-- solve(0)
      |
      |-- Move disk 1 B → C
      |
      |-- solve(0)

Output

Move disk 1 from A to B
Move disk 2 from A to C
Move disk 1 from B to C

Minimum steps = 3

Dry Run for 3 Disks

Output

Move disk 1 from A to C
Move disk 2 from A to B
Move disk 1 from C to B
Move disk 3 from A to C
Move disk 1 from B to A
Move disk 2 from B to C
Move disk 1 from A to C

Minimum steps = 7

Why Does It Work?

Every recursive call assumes:

“If I know how to move n-1 disks, then I can move n disks."

This is the essence of recursion.

Each problem becomes a smaller version of itself until there are no disks left (n = 0).

Time Complexity

The recurrence relation is

T(n) = 2T(n-1) + 1

Solving it gives

T(n) = 2ⁿ − 1

So,

• Time Complexity: O(2ⁿ)
• Space Complexity: O(n) (recursion stack)

Can We Do Better?

No.

To solve the puzzle, you must physically perform every required move. The minimum number of moves is

2ⁿ − 1

Since every algorithm has to make at least that many moves, no algorithm can have a better time complexity than O(2ⁿ).

The recursive solution is therefore asymptotically optimal.

Key Takeaways

• Don’t try to move all the disks at once.
• Focus on moving the largest disk.
• Before moving the largest disk, move all smaller disks away.
• After moving the largest disk, bring the smaller disks back.
• This repeated pattern makes recursion the natural solution.

Once you understand this pattern, many recursive problems — such as Merge Sort, Quick Sort, tree traversals, and backtracking — become much easier to understand.

Recursion isn’t about memorizing code. It’s about recognizing that a large problem can often be solved by solving a smaller version of the same problem.