Tower of Hanoi - Recursion

Tower of Hanoi:

Tower of Hanoi is a puzzle designed by Édouard Lucas, introduced in 1883. In this puzzle we have n (n can be any number: 2,3...) disks and three rods can be called as Rod 1, Rod 2, Rod 3. These rods are also called as Source(S), Destination (D) and Helper (Auxillary rod)(H) respectively.
In this puzzle, disks are initially placed on Rod 1 and disks are placed in such order that smaller disks are always placed above bigger disks (as you can see in the below image representation). We have to place all the disks from Rod 1 to Rod 2 with the help of Rod 3.
Now, let us look at the constraints and conditions of Solving the TOH puzzle. TOH puzzle can be solved using Recursion.

Conditions/Constraints:

1. No two disks can be moved at same time. In short, only one disk can be moved at a time to a rod.
2. Always, smaller disks are placed above bigger disks.
3. When moving any disk only upper disk can be moved firstly to a rod. Moving of disk other than upper placed disk is strictly prohibted.(Follow the concept of Stack LIFO)

Remember:

A Tower of Hanoi puzzle can be solved only in 2ⁿ-1 moves. (n is total number of disks).
Example: In the image below, we have taken the 3 disks So, TOH puzzle is solved in 7 Steps i.e 2³-1= 7 (steps). Similarly, if you have 2 disks, so puzzle can be solved in 3 steps.

Algorithm/Steps:

1. Move (n-1) disks from Rod 1 to Rod 3 using Rod 2. (In Image Step 3)
2. Move n^th disk from Rod 1 to Rod 3. (Print)
3. Move (n-1) disks from Rod 3 to Rod 2 using Rod 1. (In Image Step 7)

Have a Look on Image Illustration:

Code Approach: (JAVA)

package TowerOfHanoi;

public class TowerOfHanoi {
    public static void main(String[] args) {
        int n = 3; //no. of disks
        //calling TowerOfHanoi method
        TowerOfHanoi(n, "Rod1", "Rod2", "Rod3");
    }

    public static void TowerOfHanoi(int n, String Rod1, String Rod2, String Rod3) {
        if (n == 0)
            return; //recursion base case

        TowerOfHanoi(n-1,Rod1,Rod3,Rod2); //Moving n-1 disk from Rod 1 to Rod 3 using Rod 2
        System.out.println("Move disk "+n+" from "+Rod1+" to "+Rod2+" .");
        TowerOfHanoi(n-1,Rod3,Rod2,Rod1); //Moving n-1 disk from Rod 3 to Rod 2 using Rod 1
    }
}

Output:

Move disk 1 from Rod1 to Rod2 .
Move disk 2 from Rod1 to Rod3 .
Move disk 1 from Rod2 to Rod3 .
Move disk 3 from Rod1 to Rod2 .
Move disk 1 from Rod3 to Rod1 .
Move disk 2 from Rod3 to Rod2 .
Move disk 1 from Rod1 to Rod2 .