December 25, 2019 /   resursion   programming   algorithm

Tower of Hanoi is a classic problem of recursion. In this problem, you need to move disks from one tower to another with the help of a temporary tower. Disks can be placed on a tower in such a manner that no larger disk can be placed on smaller disk. It is fairly easy to solve this problem for 3 or disks using pen and paper. If we were to calculate total number of moves required to move N disks, here's how we can do that using recursion.

Suppose we have three towers A,B, C and N disks on tower A. We need to move all disks to tower C using tower A and B maintaining the constraint that a larger disk is never placed on a smaller disk.

Let's say T(N) are moves required to do this transfer. Now suppose we know, somehow, moves required when there are N-1 disks, the T(N-1).

Then we can place N-1 disks to tower B, then Nth disk to tower C, then N-1 disks from tower B to tower C. This will solve our problem.

So we have done T(N-1) moves twice and one move for Nth disk.

i.e.

T(N) = T(N-1) + 1 + T(N-1) = 2 T(N-1) + 1

where T(1) = 1 (for one disk only one move is required).

T(N) = 2 (2 T(N-2) + 1) + 1 = 4 T(N-2) + 2 + 1

if we expand this recursion we will get geometric progression

T(N) = 1 + 2 + 4 + ... + 2 ^ (N-1)

T(N) = 2^N -1

So for 5 disks we need 2^5 -1 = 31 moves.