**Write a java program to solve the Tower of Hanoi problem using Recursion.**

**Tower of Hanoi** is a game or puzzle of rods/towers in which a certain number of disks of different sizes needs to be transferred from one tower to another.

The puzzle starts with 3 different size disks in ascending order, with the smallest one at the top.

The aim is to move all the disk in the same order to destination tower abiding the following **rules**:

- One disk should be moved at a time.
- Larger disk should not be placed at the top of a smaller disk.

Initially, we have this stack

We want to achieve this by following the rules.

To solve the **Tower of Hanoi problem we will use recursion** because each subset of disks is itself follow tower of Hanoi pattern.

## Tower of Hanoi using Recursion – Algorithm

Suppose we are given 3 (n) disk as stated in the first diagram and asked to solve this using recursion. And we also know that putting large disk over small ones is not allowed.

The trick is to **assume that we are given only two disks** (as stated in the picture).

Now we need to shift the upper disk i.e n-1 (which actually contains 2 Disk in the current scenario) to B so that we can shift the last disk (n-th) to C.

The main point is we will not do this. The recursive function will take the responsibility to shift n-1 disks (2 disks in this case) to B.

`hanoi(n-1,rodFrom,rodTo,rodMiddle)`

where * rodFrom = A* ,

**and**

*rodTo = B**will be used as auxiliary rod by the recursive function.*

**rodMiddle = C**Now we need to shift last disk (nth or largest disk) to rod C. So we will do this Just by outputting the statement.

`System.out.println("Disk "+n+" moved from "+rodFrom+" to "+rodTo)`

where ** n=3**,

*and*

**rodFrom = A**

*rodTo = C**.*

Now again the n-1 disk (2 disks) in rod B need to be shifted to C with the help of rod A. Since there are multiple disk i.e n-1, so let the recursive function handle this task. So we will write

`hanoi(n-1,rodMiddle,rodFrom,rodTo)`

where * rodFrom = B* ,

**and**

*rodTo = C**will be used as auxiliary rod by the recursive function.*

**rodMiddle = A**Finally, we will get this i.e Tower of Hanoi solved.

Let’s solve the Tower of Hanoi in Java.

1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 |
class Main { public static void main(String[] args) { hanoi(3, 'A', 'B', 'C'); } private static void hanoi(int n, char rodFrom, char rodMiddle, char rodTo){ if(n==1){ System.out.println("Disk 1 moved from "+rodFrom+" to "+rodTo); return; } //Move top n-1 disks from A to B using C as middle hanoi(n-1,rodFrom,rodTo,rodMiddle); //Move last disk from A to C System.out.println("Disk "+n+" moved from "+rodFrom+" to "+rodTo); //Move n-1 disks from B to C using A as middle hanoi(n-1,rodMiddle,rodFrom,rodTo); } } |

**Output**

If you have any problem in understanding the concept or have any suggestion then comment below.