**Company tags: GOLDMAN SACHS, OYO ROOMS, SAMSUNG..etc**

The tower of Hanoi is a famous puzzle where we have three rods and **N** disks. The objective of the puzzle is to move the entire stack to another rod. You are given the number of discs **N**. Initially, these discs are in the rod 1. You need to print all the steps of discs movement so that all the discs reach the 3^{rd} rod. Also, you need to find the total moves.**Note: **The discs are arranged such that the** top disc is numbered 1 **and the** bottom-most disc is numbered N**. Also, all the discs have **different sizes** and a bigger disc **cannot** be put on the top of a smaller disc. Refer the provided link to get a better clarity about the puzzle.

**Input:**

The first line of input is **T** denoting the number of testcases. **T** testcases follow. Each testcase contains a single line of input containing **N**.

**Output:**

For each testcase, print the steps and the total steps taken. Please see the example output to see the steps format.**Please take care of the case of the letters.**

**Your Task:**

This is a function problem. You only need to complete the function toh that takes following parameters: **N** (number of discs), **Src** (The rod number from which we move the disc), **dst** (The rod number to which we move the disc),**helper** (The rod that is used as an helper rod), **moves** (reference to the moves variable to store total moves) and prints the required moves. The total number of moves are printed by the driver code.

**Expected Time Complexity: **O(2^{N}).**Expected Helper Space: **O(N).

**Constraints:**

1 <= T <= 16

1 <= N <= 16

**Example:Input:**

2

2

3

**Output:**

move disk 1 from rod 1 to rod 2

move disk 2 from rod 1 to rod 3

move disk 1 from rod 2 to rod 3

3

move disk 1 from rod 1 to rod 3

move disk 2 from rod 1 to rod 2

move disk 1 from rod 3 to rod 2

move disk 3 from rod 1 to rod 3

move disk 1 from rod 2 to rod 1

move disk 2 from rod 2 to rod 3

move disk 1 from rod 1 to rod 3

7

**Explanation:****Testcase 1:** For N=2 , steps will be as follows in the example and total 3 steps will be taken.**Testcase 2:** For N=3 , steps will be as follows in the example and total 7 steps will be taken.

Tower of Hanoi is a mathematical puzzle where we have three rods and n disks. The objective of the puzzle is to move the entire stack to another rod, obeying the following simple rules:

1) Only one disk can be moved at a time.

2) Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.

3) No disk may be placed on top of a smaller disk.

**We will solve it using recursion by doing 3 simple steps given below:**

1.First we will move* N-1* stacks form

*rod to*

**source***rod simply by calling*

**helper***function.*

**recursive**`towerOfHoni( n-1, src, helper, dst)`

2. In second Step we will move the * n’th* stack from

*rod to*

**source***rod using*

**destination****helper**rod.

`towerOfHoni(1, src, dst, helper)`

3. In last step we will move all* n-1* stacks from

**rod to the**

*helper**rod using*

**destination***rod.*

**source**`towerOfHoni( n-1, helper, dst, src)`

*S***o let’s see the code implementations:**

```
package recursion;
import java.util.Scanner;
public class TowerOfHoni {
static long moves = 0;
static void towerOfHoni(int n, int src, int dst, int helper) {
if( n >= 1) {
towerOfHoni( n-1, src, helper, dst);
System.out.println("moves disk " +n+ " form rod"+ src + " to rod" + dst );
moves++;
towerOfHoni(n-1, helper, dst, src);
}
}
public static void main(String[] args) {
Scanner sc = new Scanner(System.in);
int t = sc.nextInt();
while(t-- != 0) {
int n = sc.nextInt();
towerOfHoni(n, 1, 3, 2);
System.out.println(moves);
}
}
}
```

Hope you guys understand the solution of tower of honi in java using recursion.

* For practicing the question link is given*:https://practice.geeksforgeeks.org/problems/tower-of-hanoi/0

**Thanks for reading…!**

**Happy Coding..!**

**Thank You…!**