Java Program for Tower of Hanoi with Recursion

A Java program for Tower of Hanoi uses a recursive method like void solve(int n, char from, char to, char aux) that moves disks between rods by calling itself to move smaller stacks.

Examples

Input3 disks

OutputMove 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

Input1 disk

OutputMove disk 1 from A to C

Input0 disks

Output

How to Think About It

To solve Tower of Hanoi, think of moving the top n-1 disks to the auxiliary rod first, then move the largest disk to the target rod, and finally move the n-1 disks from auxiliary to target. Use recursion to repeat this process for smaller stacks until no disks remain.

Algorithm

1

If number of disks n is 1, move the disk from source to target and return.

2

Recursively move n-1 disks from source to auxiliary rod.

3

Move the nth disk from source to target rod.

4

Recursively move n-1 disks from auxiliary to target rod.

Code

java

public class TowerOfHanoi {
    public static void solve(int n, char from, char to, char aux) {
        if (n == 1) {
            System.out.println("Move disk 1 from " + from + " to " + to);
            return;
        }
        solve(n - 1, from, aux, to);
        System.out.println("Move disk " + n + " from " + from + " to " + to);
        solve(n - 1, aux, to, from);
    }

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

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

Dry Run

Let's trace 3 disks through the recursive calls.

1

Move top 2 disks from A to B using C

solve(2, A, B, C) called

2

Move disk 1 from A to C

Base case reached: move disk 1 from A to C

3

Move disk 2 from A to B

Print move disk 2 from A to B

4

Move disk 1 from C to B

Base case reached: move disk 1 from C to B

5

Move disk 3 from A to C

Print move disk 3 from A to C

6

Move top 2 disks from B to C using A

solve(2, B, C, A) called

7

Move disk 1 from B to A

Base case reached: move disk 1 from B to A

8

Move disk 2 from B to C

Print move disk 2 from B to C

9

Move disk 1 from A to C

Base case reached: move disk 1 from A to C

Step	Action
1	Call solve(3, A, C, B)
2	Call solve(2, A, B, C)
3	Move disk 1 from A to C
4	Move disk 2 from A to B
5	Move disk 1 from C to B
6	Move disk 3 from A to C
7	Call solve(2, B, C, A)
8	Move disk 1 from B to A
9	Move disk 2 from B to C
10	Move disk 1 from A to C

Why This Works

Step 1: Recursive Breakdown

The problem breaks down into moving smaller stacks of disks recursively using solve calls.

Step 2: Base Case

When only one disk remains, it moves directly from source to target, stopping recursion.

Step 3: Move Largest Disk

After moving smaller disks out of the way, the largest disk moves to the target rod.

Step 4: Final Moves

The smaller disks are moved from auxiliary to target rod, completing the puzzle.

Alternative Approaches

Iterative Approach Using Stack

java

import java.util.Stack;

public class TowerOfHanoiIterative {
    public static void solve(int n, char from, char to, char aux) {
        Stack<String> moves = new Stack<>();
        int totalMoves = (int) Math.pow(2, n) - 1;
        char s = from, d = to, a = aux;
        if (n % 2 == 0) {
            char temp = d; d = a; a = temp;
        }
        for (int i = 1; i <= totalMoves; i++) {
            if (i % 3 == 1) moves.push("Move disk between " + s + " and " + d);
            else if (i % 3 == 2) moves.push("Move disk between " + s + " and " + a);
            else moves.push("Move disk between " + a + " and " + d);
        }
        while (!moves.isEmpty()) System.out.println(moves.pop());
    }

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

This uses an iterative method with stacks but is more complex and less intuitive than recursion.

Using Memoization to Store Moves

java

import java.util.ArrayList;
import java.util.List;

public class TowerOfHanoiMemo {
    static List<String> moves = new ArrayList<>();
    public static void solve(int n, char from, char to, char aux) {
        if (n == 1) {
            moves.add("Move disk 1 from " + from + " to " + to);
            return;
        }
        solve(n - 1, from, aux, to);
        moves.add("Move disk " + n + " from " + from + " to " + to);
        solve(n - 1, aux, to, from);
    }

    public static void main(String[] args) {
        solve(3, 'A', 'C', 'B');
        moves.forEach(System.out::println);
    }
}

Stores all moves in a list before printing, useful for further processing but uses extra memory.

Complexity: O(2^n) time, O(n) space

Time Complexity

The algorithm makes 2^n - 1 moves, so time grows exponentially with the number of disks.

Space Complexity

Space is O(n) due to recursion call stack depth equal to the number of disks.

Which Approach is Fastest?

Recursive approach is simplest and efficient for this problem; iterative methods are more complex without speed benefits.

Approach	Time	Space	Best For
Recursive	O(2^n)	O(n)	Simplicity and clarity
Iterative with Stack	O(2^n)	O(n)	Avoiding recursion but more complex
Memoization	O(2^n)	O(n + 2^n)	Storing moves for later use