🚀Day 20/180 Tower of Hanoi.(Using Recursive function)

Tower of Hanoi

#180DaysOfDSA#DailyCodingChallenge #LeetCodeJourney #GeeksforGeeks #CodingNinjas #Codechef #CodeForces #ContinuousLearning #TechCommunity

public class Main{
public static void towerOfHanoi(int n, String src, String helper, String dest) {
if(n == 1) {
System.out.println("transfer disk " + n + " from " + src + " to " + dest);
return;
}

//transfer top n-1 from src to helper using dest as 'helper'
towerOfHanoi(n-1, src, dest, helper);
//transfer nth from src to dest
System.out.println("transfer disk " + n + " from " + src + " to " + helper);
//transfer n-1 from helper to dest using src as 'helper'
towerOfHanoi(n-1, helper, src, dest);
}
public static void main(String args[]) {
int n = 4;
towerOfHanoi(n, "A", "B", "C");
}
}
/*
 * PS C:\Users\HP\OneDrive\Coding\Java\Practice01> javac Main.java
PS C:\Users\HP\OneDrive\Coding\Java\Practice01> java Main
transfer disk 1 from A to B
transfer disk 2 from A to B
transfer disk 1 from B to C
transfer disk 3 from A to C
transfer disk 1 from C to A
transfer disk 2 from C to A
transfer disk 1 from A to B
transfer disk 4 from A to B
transfer disk 1 from B to C
transfer disk 2 from B to C
transfer disk 1 from C to A
transfer disk 3 from B to A
transfer disk 1 from A to B
transfer disk 2 from A to B
transfer disk 1 from B to C
 */

DRY RUN :

Dry run of the corrected Tower of Hanoi implementation for ( n = 3 ). This will help illustrate how the recursive calls work.

The initial call is towerOfHanoi(3, "A", "B", "C").

Step-by-Step Dry Run:

1. Call: towerOfHanoi(3, "A", "B", "C")

   • Recursively call: towerOfHanoi(2, "A", "C", "B")

     • Recursively call: towerOfHanoi(1, "A", "B", "C")

       • Base case: Move disk 1 from A to C

     • Move: Disk 2 from A to B

     • Recursively call: towerOfHanoi(1, "C", "A", "B")

       • Base case: Move disk 1 from C to B

   • Move: Disk 3 from A to C

   • Recursively call: towerOfHanoi(2, "B", "A", "C")

     • Recursively call: towerOfHanoi(1, "B", "C", "A")

       • Base case: Move disk 1 from B to A

     • Move: Disk 2 from B to C

     • Recursively call: towerOfHanoi(1, "A", "B", "C")

       • Base case: Move disk 1 from A to C

Dry Run Details:

1. First Call: towerOfHanoi(3, "A", "B", "C")

   • Call: towerOfHanoi(2, "A", "C", "B")

     • Call: towerOfHanoi(1, "A", "B", "C")

       • Move disk 1 from A to C

       • Output: transfer disk 1 from A to C

     • Move disk 2 from A to B

     • Output: transfer disk 2 from A to B

     • Call: towerOfHanoi(1, "C", "A", "B")

       • Move disk 1 from C to B

       • Output: transfer disk 1 from C to B

   • Move disk 3 from A to C

   • Output: transfer disk 3 from A to C

   • Call: towerOfHanoi(2, "B", "A", "C")

     • Call: towerOfHanoi(1, "B", "C", "A")

       • Move disk 1 from B to A

       • Output: transfer disk 1 from B to A

     • Move disk 2 from B to C

     • Output: transfer disk 2 from B to C

     • Call: towerOfHanoi(1, "A", "B", "C")

       • Move disk 1 from A to C

       • Output: transfer disk 1 from A to C

The final output sequence for ( n = 3 ) is:

transfer disk 1 from A to C
transfer disk 2 from A to B
transfer disk 1 from C to B
transfer disk 3 from A to C
transfer disk 1 from B to A
transfer disk 2 from B to C
transfer disk 1 from A to C

This dry run verifies the correctness of the algorithm for ( n = 3 ).