Java With Us

Towers of Hanoi in Java (Recursive Solution)

Updated on 2026-04-20 Reviewed by the Java With Us editorial team

The Towers of Hanoi is a classic programming exercise that illustrates recursion beautifully. The puzzle: given three rods and n disks of different sizes stacked on the first rod in decreasing order, move the entire stack to the third rod, obeying two rules:

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

The recursive insight

To move n disks from A (source) to C (destination) using B (auxiliary), you only need to:

  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).

Steps 1 and 3 are smaller instances of the same problem — the recursion bottoms out at n = 1, where a single disk is moved directly.

Java implementation

public class TowersOfHanoi {

    public static void solve(int n, char source, char auxiliary, char destination) {
        if (n == 1) {
            System.out.printf("Move disk 1 from %c to %c%n", source, destination);
            return;
        }
        // Step 1: move top n-1 disks from source to auxiliary
        solve(n - 1, source, destination, auxiliary);

        // Step 2: move the largest remaining disk
        System.out.printf("Move disk %d from %c to %c%n", n, source, destination);

        // Step 3: move the n-1 disks from auxiliary to destination
        solve(n - 1, auxiliary, source, destination);
    }

    public static void main(String[] args) {
        int n = 3;
        solve(n, 'A', 'B', 'C');
    }
}

Sample output for n = 3:

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

Why exactly 7 moves?

The minimum number of moves for n disks is 2n − 1:

  • n = 1 → 1 move
  • n = 3 → 7 moves
  • n = 10 → 1 023 moves
  • n = 64 → about 585 billion years at one move per second (the original legend)

Time complexity is therefore O(2n), space complexity is O(n) — the depth of the recursion stack.

Counting the moves

public static int countMoves(int n, char source, char aux, char dest) {
    if (n == 1) return 1;
    return countMoves(n - 1, source, dest, aux)
         + 1
         + countMoves(n - 1, aux, source, dest);
}

public static void main(String[] args) {
    for (int n = 1; n <= 10; n++) {
        System.out.println(n + " disks → " + countMoves(n, 'A', 'B', 'C') + " moves");
    }
}

Iterative variant

An iterative solution exists using an explicit stack or clever bitwise reasoning. It is less elegant but avoids deep recursion for large n:

public static void solveIterative(int n) {
    Deque<int[]> stack = new ArrayDeque<>();
    // Frame format: {n, source, aux, dest, stage}
    stack.push(new int[]{n, 'A', 'B', 'C', 0});
    while (!stack.isEmpty()) {
        int[] f = stack.peek();
        if (f[0] == 1) {
            System.out.printf("Move disk 1 from %c to %c%n", f[1], f[3]);
            stack.pop();
        } else if (f[4] == 0) {
            f[4] = 1;
            stack.push(new int[]{f[0] - 1, f[1], f[3], f[2], 0});
        } else if (f[4] == 1) {
            System.out.printf("Move disk %d from %c to %c%n", f[0], f[1], f[3]);
            f[4] = 2;
            stack.push(new int[]{f[0] - 1, f[2], f[1], f[3], 0});
        } else {
            stack.pop();
        }
    }
}

Takeaway

Towers of Hanoi is a beautiful minimal example of divide-and-conquer: each call decomposes the problem into two strictly smaller identical subproblems plus one constant-cost operation. If you are learning recursion, implement it from scratch, then try variants (four pegs, non-adjacent moves only, counting disk moves per rod) to deepen your intuition.

Related articles