Towers of Hanoi

The 'Towers of Hanoi' is a classical problem used to illustrate the power of recursion. 

Problem Explanation:- There are 3 pegs say A, B and C. Peg A is starting peg, Peg B is intermediate peg and Peg C is destination peg. Peg A has disc of different size. Each disc are of different size (i.e. no two disc can be of same size) and smaller disc should always be on top of big disc. We need to move disc from peg A to peg C with small disc on top and big disc at the bottom.

Lets take example with Peg A having 2 disc.

In order to move all disc from Peg A to Peg C  in same order using intermediate Peg B. First, 

move disc 1 from Peg A to Peg B

          disc 2 from Peg A to Peg C

          disc 1 from Peg B to Peg C

Now try the above step with Peg A having 3 disc.

• Move 2 disc (i.e. disc 1 and disc 2 ) from Peg A to Peg B as above example (consider Peg C as intermediate Peg)
• Move disc 3 to Peg C
• Move disc 1,2 from Peg B to Peg C  (consider Peg A as intermediate Peg)

Similarly, we have to follow 3 step for n disc are as follows:

• Move (n-1) disc from Peg A to Peg B (Peg C as intermediate Peg)
• Move n th disk from Peg A to Peg C
• Move (n-1) disc from Peg B to Peg C (Peg A as intermediate Peg)

Now we will translate the above steps to programming steps:

 public void solve(int n, String startPeg, String intermediatePeg, String endPeg){
  if(n==1){
   System.out.println(startPeg +"--->>>"+endPeg);
  }else{
   /*
    * step 1: end Peg will act as intermediate Peg and intermediate 
    * Peg will become end Peg.
    */
   solve(n-1,startPeg,endPeg, intermediatePeg);
   
   /*
    * Step 2: move n th disk from start peg to end peg
    */
   System.out.println(startPeg +"--->>>"+endPeg);
   
   /*
    * Step 3: intermediate peg will act as start peg and start peg will act as 
    * intermediate peg
    */
   solve(n-1, intermediatePeg, startPeg, endPeg);
  }
 }

Time Complexity:

from the above steps
          T(n) = T(n-1) + C + T(n-1)
          i.e.  time complexity for n disc = [time complexity for n-1 disc in step1] + [constant time need to move disc from start peg to end peg] +  [time complexity for n-1 disc in step3]

           T(n-1) = 2T(n-1)+ C (C is constant so consider it as 1)
           T(n-1) = 2T(n-1)+ 1
                      = 2( 2T(n-2) + 1 ) + 1
                      = 4T(n-2)+2+1
                      =4(2T(n-3) +1) + 2 + 1
                      =8T(n-3) +4 + 2 +1
                      = (2^n)T(n-n) + (2^(n-1)) + ......+ 4 + 2 + 1 (let T(0) = 0)
                      = (2^(n-1)) + ......+ 4 + 2 + 1
                      = (2^n)-1 = O(2^n)