Recurrence 1.1 : The Tower of Hanoi

Problem Statement:

We are given a tower of eight disks which are arranged in decreasing size on one of the 3 pegs as shown below. The aim is to transfer the entire tower to one of the other pegs and identify the number of moves required for this movement. The puzzle is constrained around the fact that we need to make sure: 

• Only one disk can be moved at a time.
• Never should a larger disk be moved on top of a smaller one.

Smaller sub-problems:

Let us scale down the problem size from 8 disks. We will consider 0, 1 and 2 disks as our sub-problems.

• n = 0 then number of moves required = 0 (no disk)
• n = 1 then number of moves required = 1 (directly move to the destination peg)
• n = 2, number of moves required = 3
• Move the top most disk to the non destination peg.
• Move the bottom disk to the destination peg. 
•  Move the disk from non destination peg to the destination peg which will make sure the entire tower of 2 disks has been moved to the destination peg obeying our constraints.

Generalization and Recurrence relation:

Let us consider that moving n disks to the destination peg will require a minimum of T(n) moves. So, we have T(0) = 0; T(1) = 1 and T(2) = 3 based on our inspection of the smaller cases. 

By applying the perspective that we have gained to these smaller problems and based on the solution for T(2) = 3 we can state that for transferring n disks in general : 

• We first transfer the top (n - 1 disks onto the non destination peg (which requires T(n - 1) moves).
• We then transfer the largest disk at the bottom to the destination peg requiring 1 move.
• We then move all the n-1 disks to the destination peg (which requires another T(n-1) moves).

 

Above generalization leads to following recurrence relations for n disks:

    T(n) = 0  { n = 0 };

    T(n) = 2*T(n-1) + 1 { n > 0 }

Solving the recurrence:

The recurrence relation above allows us to compute the number of moves required T(n) for moving n disks. The solution to the above recurrence would help us instantaneously calculate number of moves required for large values of n.

So, we compute successively as follows : 

T(0) = 0; 

T(1) = 2 * T(0) + 1 = 1 ; 

T(2) = 2 * T(1) + 1 = 2 * 1 + 1 = 3; 

T(3) = 2 * T(2) + 1 = 2 * 3 + 1 = 7;

T(4) = 2 * T(3) + 1 = 2 * 7 + 1 = 15;

T(5) = 2 * T(4) + 1 = 2 * 15 + 1 = 31 and so on ........

The solution to our recurrence seems to be :

T(n) = 2^n - 1 { n >= 0 }

Thus, for n = 8, we will require 2^8 - 1 = 255 moves. 

If we consider that each move takes 1 second then the total time to make 255 moves is equal to 255 seconds which around 4 minutes.