Tower of Hanoi in Java Using Recursion

What is Tower of Hanoi ?

Tower of Hanoi is also called as Tower of Brahma or Lucas Tower. It is one of the most popular problem which makes you understand the power of recursion.  Tower of Hanoi is a mathematical puzzle which consist of 3 poles and number of discs of different sizes. Initially all the discs will be places in the single pole with the largest disc at the bottom and smallest on the top. We need to move all the disc from the first pole to the third pole with the smallest disc at the top and the largest at the bottom under the below conditions

1. Only one disc can be moved at a time.
2. Larger disc cannot be placed on a smaller disc.

Tower of Hanoi algorithm

We will using Java Recursion to solve this problem and the below step will be performed. Let’s assume there are ‘n’ discs and 3 poles (pole1, pole2, pole3)

Step 1: Move (n-1) discs from pole1 to pole2
Step 2: Move the nth disc (last disc) from pole1 to pole3.
Step 3: Now move the n-1 discs which is present in pole2 to pole3.

Step1 and Step3 will be recursive. Lets take a look into the below Java code, where we have implemented the Tower of Hanoi algorithm using recursion.

package com.javainterviewpoint;

import java.util.Scanner;

public class TowerOfHanoi
{
    public static void shift(int n, String startPole, String intermediatePole, String endPole)
    {
        if (n == 0)
        {
            return;
        }
        shift(n - 1, startPole, endPole, intermediatePole);
        System.out.println("Move \"" + n + "\" from " + startPole + " --> " + endPole);
        shift(n - 1, intermediatePole, startPole, endPole);
    }
    public static void main(String[] args)
    {
        System.out.print("Enter number of discs: ");
        Scanner scanner = new Scanner(System.in);
        int numberOfDiscs = scanner.nextInt();
        shift(numberOfDiscs, "Pole1", "Pole2", "Pole3");
    }
}

In our TowerOfHanoi class we have shift() method which will be recursively called. It takes up 4 parameters n(number of discs), startPole, intermediatePole, endPole are the three poles which will be used for swapping.

We will start the recursion by swapping the n-1 disc from the startPole to the intermediatePole, followed by moving the disc from intermediatePole to the endPole. This will be continued until n is equal to ‘zero’.

Output :

Enter number of discs: 5

Move “1” from Pole1 –> Pole3
Move “2” from Pole1 –> Pole2
Move “1” from Pole3 –> Pole2
Move “3” from Pole1 –> Pole3
Move “1” from Pole2 –> Pole1
Move “2” from Pole2 –> Pole3
Move “1” from Pole1 –> Pole3
Move “4” from Pole1 –> Pole2
Move “1” from Pole3 –> Pole2
Move “2” from Pole3 –> Pole1
Move “1” from Pole2 –> Pole1
Move “3” from Pole3 –> Pole2
Move “1” from Pole1 –> Pole3
Move “2” from Pole1 –> Pole2
Move “1” from Pole3 –> Pole2
Move “5” from Pole1 –> Pole3
Move “1” from Pole2 –> Pole1
Move “2” from Pole2 –> Pole3
Move “1” from Pole1 –> Pole3
Move “3” from Pole2 –> Pole1
Move “1” from Pole3 –> Pole2
Move “2” from Pole3 –> Pole1
Move “1” from Pole2 –> Pole1
Move “4” from Pole2 –> Pole3
Move “1” from Pole1 –> Pole3
Move “2” from Pole1 –> Pole2
Move “1” from Pole3 –> Pole2
Move “3” from Pole1 –> Pole3
Move “1” from Pole2 –> Pole1
Move “2” from Pole2 –> Pole3
Move “1” from Pole1 –> Pole3