**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

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

**Tower of Hanoi algorithm**

We will be 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

## Leave a Reply