The Tower Of Hanoi

The Tower Of Hanoi problem is perhaps the most frequently asked recursion-based problem in interviews and examinations. Perhaps the most succinct explanation of this problem can be found in Wikipedia here .

PROBLEM STATEMENT :
A set of n disks are kept on a peg A such that each disk lies on top of a disk larger in size than it. This set of disks is to be moved to another peg B; always minding the consistency that a smaller disk lies on a larger disk. We can use an auxiliary peg C for our aid.

ALGORITHM :
We use recursion to solve the problem. Consider an auxiliary function moveTower that accepts the parameters sourceTower, destTower, auxTower and numberOfDisks. This function moves numberOfDisks disks (<= n) from the sourceTower to the destTower using the auxTower. We follow the recursive idea that in order to move n disks from A to B using C as auxiliary, we move the top n-1 disks from A to C using auxiliary and then move the remaining 1 disk (the largest disk) from A to B. The problem now shortens to moving n-1 disks from C to B using A as auxiliary. Thus we see that after each iteration, the problem gets smaller and thus there will be a terminating condition. The terminating condition of the recursion is that n becomes 1. 1 disk can be moved in 1 move.

Algorithm moveTower (sourceTower, destTower, auxTower, numberOfDisks)

1. if (numberOfDisks == 1) then move disk from sourceTower to destTower and exit //terminating condition
2. else{
3.      moveTower(sourceTower, auxTower, destTower, numberOfDisks - 1)
4.      moveTower(sourceTower, destTower, auxTower, 1)   
5.      moveTower(auxTower, destTower, sourceTower, numberOfDisks-1)
6. } if - else ends 

The java code that simulates the Tower Of Hanoi problem is as follows:

ANALYSIS :
If T(n) is the time required to transfer n disks from sourceTower to destTower, then by the above algorithm, T(n) is distributed into 2 transfers of  n-1 disks and a transfer of 1 disk. Thus,
                                                 T(n) =  2T(n-1) + T(1)
But how many moves do we require to transfer n disks from A to B? We can prove by mathematical induction that the minimum number of moves required are 2ⁿ - 1. The 3 steps of mathematical induction are :

1. Basic Case : For n = 1 i.e if there is only 1 disk, then we directly transfer the disk from A to B in 1 move. 2¹ - 1 = 1. Hence, the equation holds true for the base case.
2. Assumption : We now assume that the equation holds true for all integers 1 to n-1.
3. Induction : Since the relation holds true for integers from 1 to n-1, we now check the relation for n number of disks. To transfer n disks from A to B, we first move n-1 disks from A to C in 2^n-1 - 1 moves, then transfer 1 disk from A to B in 1 move and lastly move n-1 disks from C to B in 2^n-1 - 1 moves. Thus, the total number of moves are 2^n-1 - 1 + 2^n-1 - 1 + 1 = 2*2^n-1 - 1 =
   2ⁿ - 1. Thus, we have "induced" the relation to all integers.

The Tower Of Hanoi problem is the best example where the advantages of using a recursive method far outweighs its disadvantages. While recursion may not be advisable in cases of problems like the Fibonacci series because of the overhead in calling a function recursively and maintaining stacks of duplicate variables, recursion proves to be a boon in Tower Of Hanoi and is, indeed, in many aspects better than the iterative method.