INTUITION BEHIND THE TOWER OF HANOI AND THE RECURSION I

 INTRODUCTION ... 

Problem statement says there is a rod say A in which some disks of different sizes placed in such a way that smaller disks are above the larger disks. You have assign a job to shift all the disks from A to another rod say C with the help of an auxiliary rod say B. (as shown in figure) provided that at any stage of arranging , arrangement shouldn't violates the property of arrangement (i.e., Bigger disk shouldn't placed above the smaller disk) .

   

IMPORTANCE OF THE PROBLEM....

The solution of problem of the TOWER OF HANOI gives the clear picture of the working principle of the Recursion. 

First of all , lets talk about the basic principle of Recursion using an interesting example...

Assume a job to build a five floored building is assign to the group of 6 workers . Here each worker is as much efficient that a single worker can build single floor. 

The proposal is first given to 1st worker then worker replied if somehow first four floor built then I can build the 5th floor.

Now the proposal to build the first four floor given to the 2nd worker then he also replied if somehow first three floor built then I can build the 4th floor.

Similar situation is happen till the Second last worker..

Now when the proposal to build the ground floor is given to the last worker , then that particular worker has no any option to refer the work to the other and he agree to build the ground floor . After that 2nd last worker build the 1st floor and similarly at last 1st worker finish 5th floor and finally the work is Finished. 

The process that discussed in the above example is nothing but the RECURSION. So if the entire process is divided into sub problems then Recursion come into the picture..  BUT WAIT..    if the problem divided into sub problems then there should be a condition where the division should be stop . In the above example stopping condition is the formation of the GROUND FLOOR . This stopping condition is known as BASE CASE.

Hence to solve the problem using the RECURSION , two thing is most important...

1. THE RECURRENCE RELATION that helps to divide the Problem into the subproblem

2. THE BASE CASE to stop the dividing and start to solve in upward direction.

HOW RECURSION WILL HELPFUL TO THE PROBLEM OF TOWER OF HANOI......

Lets start think from the base case..... 

If we have only one disk in the Rod  A then we can put it directly into the Rod C without using the Auxiliary Rod B . 

If we have two disks in Rod A then first we can put the first disk into Rod B and put the second disk into the Rod C then finally shift the the disk from Rod B to Rod C. But what would be the Procedure if there are three disks in Rod A ???? 

Okay first analyse what we have done till now...  We have two disk in the Rod A and we shift the 1st disk into auxiliary Rod then shift the last disk into the final Rod and finally shift the disk from the auxiliary Rod to the final Rod.

Move to the RECURSION...

If there are 3 disk , then someone can say that if anyone can put 1st two disk into the Auxiliary Rod then I shift the the last disk into the final rod and again shift all other disks from auxiliary rod to Final Rod.

In general sense , If there are N disks into the Rod A , then first N-1 rod into the Auxiliary Rod and move Nth rod into the Final Rod and finally shift N-1 disks from Auxiliary Rod to the Final rod. The base case will occur if when there is only one disk is present into the Rod A.

THIS IS THE OVERVIEW OF RECURSION AND THE DISCUSSION OF APPROACH TO SOLVE TOWER OF HANOI. THE CODE AND MECHANISM OF SOLUTION OF TOWER OF HANOI IS HERE

THANKS....