The Tower of Hanoi is a classic mathematical puzzle that elegantly demonstrates the power of recursion. It consists of three rods (pegs) and a number of disks of different sizes that can slide onto any rod. The puzzle begins with all disks stacked in ascending size order on one rod (smallest on top) and the goal is to move the entire stack to another rod.

Three rules must be followed:

1. Only one disk may be moved at a time.
2. A disk may only be moved if it is the uppermost disk on its rod.
3. No disk may be placed on top of a smaller disk.

The minimum number of moves required to solve the puzzle with n disks is 2ⁿ − 1. For 3 disks, that’s 7 moves; for 10 disks, 1023 moves.

Recursive Solution

To move n disks from rod A to rod C using rod B as auxiliary:

1. Move the top n−1 disks from A to B (using C as auxiliary).
2. Move the largest disk from A to C.
3. Move the n−1 disks from B to C (using A as auxiliary).

Java Program: Tower of Hanoi

import java.io.*;

public class TowerOfHanoi {
    static int moveCount = 0;  // Tracks the total number of disk moves made

    public static void main(String[] args) throws IOException {
        BufferedReader reader = new BufferedReader(new InputStreamReader(System.in));
        System.out.print("Enter number of disks: ");
        int numDisks = Integer.parseInt(reader.readLine());

        System.out.println("\nSteps to solve Tower of Hanoi with " + numDisks + " disk(s):");
        solveHanoi(numDisks, 'A', 'C', 'B');

        moveCount++;
        System.out.println("\nTotal number of moves: " + moveCount);
    }

    /**
     * Recursively solves Tower of Hanoi.
     *
     * @param numDisks  Number of disks to move
     * @param fromRod   The source rod (where disks currently are)
     * @param toRod     The target rod (where disks should go)
     * @param auxRod    The auxiliary/helper rod
     */
    static void solveHanoi(int numDisks, char fromRod, char toRod, char auxRod) {
        if (numDisks == 1) {
            // Base case: only one disk - move it directly from source to target
            System.out.println("Move disk 1 from rod " + fromRod + " to rod " + toRod);
        } else {
            // Step 1: Move top (n-1) disks from source to auxiliary
            solveHanoi(numDisks - 1, fromRod, auxRod, toRod);

            // Step 2: Move the nth (largest) disk from source to target
            System.out.println("Move disk " + numDisks + " from rod " + fromRod + " to rod " + toRod);
            moveCount++;

            // Step 3: Move the (n-1) disks from auxiliary to target
            solveHanoi(numDisks - 1, auxRod, toRod, fromRod);
            moveCount++;
        }
    }
}

How the Code Works

1. Input — The number of disks is read from the console.
2. solveHanoi(n, A, C, B) — Called with source rod A, target rod C, and auxiliary rod B. This initial call produces the complete move sequence for all n disks.
3. Base case (n == 1) — A single disk is moved directly from fromRod to toRod.
4. Recursive case — First, the top n−1 disks are moved to the auxiliary rod. Then the largest disk is moved to the target rod. Finally, the n−1 disks are moved from the auxiliary rod to the target rod.
5. Move count — Each recursive non-base call represents two disk moves (steps 2 and 3). The total for n disks equals 2ⁿ − 1.

Sample Output

Enter number of disks: 3

Steps to solve Tower of Hanoi with 3 disk(s):
Move disk 1 from rod A to rod C
Move disk 2 from rod A to rod B
Move disk 1 from rod C to rod B
Move disk 3 from rod A to rod C
Move disk 1 from rod B to rod A
Move disk 2 from rod B to rod C
Move disk 1 from rod A to rod C

Total number of moves: 7

Output Explanation

With 3 disks labelled 1 (smallest) to 3 (largest), all starting on rod A:

• Move 1: Disk 1 A → C (frees disk 2 on rod A).
• Move 2: Disk 2 A → B.
• Move 3: Disk 1 C → B (places disk 1 on top of disk 2).
• Move 4: Disk 3 A → C (the biggest disk reaches its final position).
• Move 5: Disk 1 B → A (frees disk 2 on rod B).
• Move 6: Disk 2 B → C (disk 2 reaches its final position).
• Move 7: Disk 1 A → C (disk 1 completes the puzzle).

Total moves = 2³ − 1 = 7. ✓

See Also

• Implementing Binary Search Tree in Java — Another recursive data structure algorithm
• Implementing Quick Sort in Java — Recursive divide-and-conquer sorting algorithm
• Implementation of Stack in Java — Recursion is powered by the call stack internally

Conclusion

The Tower of Hanoi puzzle is a textbook example of recursion — a problem that is extremely difficult to solve iteratively but becomes trivially elegant when expressed recursively. The solution cleanly decomposes into three steps that mirror the structure of the problem itself. Understanding this recursive pattern is key to mastering other divide-and-conquer algorithms like merge sort, quicksort, and tree traversals.