INTUITION BEHIND THE TOWER OF HANOI AND THE RECURSION II

 The statement and condition of the problem TOWER OF HANOI and the Idea behind the recursion is already discussed. Reader can check it  HERE .

IF YOU ARE USING SMARTPHONE.. PLEASE ROTATE THE SMARTPHONE IN LANDSCAPE MODE FOR BETTER VIEWING..

Now we move to the solution of the problem TOWER OF HANOI...

Here our task is to displace all the disk from start rod (A) to end rod(C) with the help of middle(B). For this first we move all three disks from start(A) to middle(B) then move the fourth disk directly from start(A) to end(C) and again shift the first three disks from middle rod(B) to end rod(C).

So our task is reduced to put first three disks from start(A) to middle(B). for this , we can use the end rod(C) as the helping rod. For performing this task , we have to put first two rod from start rod(A) to end rod(C).

Now our task is reduced . We have to just put the first two rod from start rod(A) to end rod (C). For this , we can use the middle rod(B) as the helping rod. So our task is to put the first disk in middle rod(B), then we can shift the second disk in the end rod(C) then we can shift the first disk from the middle rod(B) to end rod(C). So finally We have shifted first two disk so we can shift the third disk from first rod(A) to middle rod(B). Now we can shift the first two disk from end rod(C) to middle rod(B) by the same process.

After shifting the first three disk from start rod(A) to End middle rod(B), we can shift the last disk directly from start rod(A) to end rod (C). After shifting the last rod , We can shift the remaining three rod from middle rod(B) to end rod(C) by applying the procedure that we've done for the shifting from start(A) to middle rod (B).

Now lets analyse the whole procedure.

 

 Our task was  to shift the all disk from start(A) to End rod(C)... Then 

step 1.. Shift the first three rod from start rod(A) to middle(B)

step 2. Shift the fourth rod from start(A) to End rod(C)

step 3. Shift the first three rod from middle rod(B) to end rod(C)...

Now in sense of Programming , We make a function/ Method named as SHIFT(.... , .... , ....)

that will give us the sequence of jumps required to shift the given number disks of TOWER OF HONOI from initial rod to final rod with the help of Auxiliary or middle rod.

So, What would be the argument that we've to pass in the function/method SHIFT(?,?,?,?)

Obviously, TO shift the disks from initial rod to final rod , We should have the Knowledge of these parameters....

1. What is Initial rod...

2. What is Destination rod...

3. What is Helping rod...

4. Number of disks in the Initial rod...

So lets assume , We have n disks in the initial rod...

Pseudo code  ....

SHIFT(initial_rod , final_rod , helping_rod , N_O_D){

SHIFT(initial_rod , helping_rod , final_rod, N_O_D - 1)// The first step of our analysis

print(move the N_O_Dth disk from initial_rod to final_rod  )//second step of our analysis 

SHIFT(helping_rod , final_rod , initial_rod , N_O_D - 1)// The third step of our analysis

}

Is THIS PSEUDO CODE CORRECT ????

The answer is NO. Since SHIFT() function/method calls itself again and again... i.e., SHIFT() is a recursive function / method . So to avoid the infinite calling of SHIFT() , We need a BASE CASE...  So the next question is WHAT WOULD BE THE BASE CASE ??

Again , It's not hard to think about the base case...  Lets think at the basic situation.. 

WHAT HAPPENED IF THERE IS SINGLE DISK IN THE INITIAL ROD???

Simply shift that disk from INITIAL rod to FINAL rod. There is no need of recursion at that situation..

so the correct PSEUDO CODE IS ........

HERE N_O_D stands for number of discs...

SHIFT(initial_rod , final_rod , helping_rod , N_O_D){

if(N_O_D == 1){

print(move the N_O_Dth from initial_rod to final_rod  )

return // This line ensures that SHIFT is not going beyond the bracket.

}

SHIFT(initial_rod , helping_rod , final_rod, N_O_D - 1)// The first step of our analysis

print(move the N_O_Dth disk from initial_rod to final_rod  )//second step of our analysis 

SHIFT(helping_rod , final_rod , initial_rod , N_O_D - 1)// The third step of our analysis

}

Now it's the time for real code....

IN C++...

#include <iostream>

using namespace std;

void SHIFT(char initial_rod , char final_rod , char helping_rod , int N_O_D){

    if(N_O_D == 1)

    {

cout<<"Move the "<<N_O_D<<"st disk from "<<initial_rod<<" to "<<final_rod<<endl;

      return; 

      }

      

      SHIFT(initial_rod, helping_rod , final_rod , N_O_D - 1);

cout<<"Move the "<<N_O_D<<" th disk from "<<initial_rod<<" to "<<final_rod<<endl;

     SHIFT(helping_rod, final_rod , initial_rod , N_O_D - 1);

}

int main() {

   int N_O_D = 4; // let there are 4 disk in initial rod

   char initial_rod = 'A';// this is the initial rod

   char final_rod = 'C'; // this is final the rod

   char helping_rod =  'B';// this is helping rod

   

   SHIFT(initial_rod , final_rod , helping_rod , N_O_D);// calling of SHIFT ()

    return 0;

}

OUTPUT ::

Move the 1st disk from A to B

Move the 2 th disk from A to C

Move the 1st disk from B to C

Move the 3 th disk from A to B

Move the 1st disk from C to A

Move the 2 th disk from C to B

Move the 1st disk from A to B

Move the 4 th disk from A to C

Move the 1st disk from B to C

Move the 2 th disk from B to A

Move the 1st disk from C to A

Move the 3 th disk from B to C

Move the 1st disk from A to B

Move the 2 th disk from A to C

Move the 1st disk from B to C

THANK YOU SO MUCH...