Tower of Hanoi in Java

intermediate· Recursion · Recursion

Problem

The Tower of Hanoi puzzle moves a stack of disks from one peg to another, one disk at a time, using a third peg to help, under the rule that a larger disk can never sit on top of a smaller one.

Given a number of disks, move them all from a source peg to a destination peg using an auxiliary peg, printing every individual move.

Input

3 disks, from A to C using 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

Java Program

Java

public class TowerOfHanoi {
    static void hanoi(int n, char from, char aux, char to) {
        if (n == 0) return; // base case: no disks to move
        hanoi(n - 1, from, to, aux); // move n-1 disks out of the way
        System.out.println("Move disk " + n + " from " + from + " to " + to);
        hanoi(n - 1, aux, from, to); // move those n-1 disks onto the target
    }

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

▶ Run Code

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

Core Logic

Moving the top n - 1 disks out of the way first, then moving the single largest disk, then moving those n - 1 disks on top of it, solves the whole stack by reducing it to two smaller versions of the same puzzle.

How It Works

1hanoi(n, from, aux, to) moves n disks from the from peg to the to peg, using aux as the spare.
2The base case if (n == 0) return; does nothing, since there's no disk to move.
3hanoi(n - 1, from, to, aux) shifts the smaller disks onto the auxiliary peg first, clearing the way for the largest disk.
4After printing the move of disk n itself from from to to, hanoi(n - 1, aux, from, to) moves those same smaller disks from the auxiliary peg onto the destination, on top of the disk that just landed.

For 3 disks, the smallest disk moves three separate times, weaving between pegs, while the largest disk moves exactly once — straight from A to C — right in the middle of the sequence.

💡

Key Point: The roles of the three pegs swap between recursive calls — the auxiliary peg for one call becomes the source or destination for the next — which is what lets the same three-parameter method solve every sub-problem without extra bookkeeping.

Complexity

Time Complexity: O(2ⁿ)Space Complexity: O(n)

Why: Each additional disk doubles the number of moves needed — 2ⁿ - 1 in total — while the recursion only ever nests n calls deep at once.

Key Concepts

recursionbase casepeg juggling

← Previous

Sum of Numbers Using Recursion

Related Programs

Recursionbeginner

Array Sum Using Recursion

Recursionbeginner

Check Palindrome Using Recursion

Recursionbeginner

Factorial Using Recursion

Recursionbeginner

Factorial

Recursionintermediate

Fibonacci Sequence