Tower of Hanoi (recursion)

TOWER OF HANOI

The tower of Hanoi is one of the main applications of recursion. It says, 'if you can solve n-1 cases, then you can easily solve the n^th case'.

Look at Figure 4.12 which shows three rings mounted on pole A. The problem is to move all these rings from pole A to pole C while maintaining the same order. The main issue is that the smaller disk must always come above the larger disk.

We will be doing this using a spare pole. In our case, A is the source pole, C is the destination pole, and B is the spare pole. To transfer all the three rings from A to C, we will first shift the upper two rings (n-1 rings) from the source pole to the spare pole. We move the first two rings from pole A to B as shown in Figure 4.13.

Now that n-1 rings have been removed from pole A, the n^th ring can be easily moved from the source pole (A) to the destination pole (C). Figure 4.14 shows this step. The final step is to move the n-1 rings from B to C using A as the spare pole. This is shown in Figure 4.15.

To summarize, the solution to our problem of moving n rings from A to C using B as spare can be given as:

Base case: if n=1

• Move the ring from A to C using B as spare

Recursive case:

• Move n-1 rings from A to B using C as spare

• Move the one ring left on A to C using B as spare

• Move n-1 rings from B to C using A as spare

The following code implements the solution of the Tower of Hanoi problem.

#include <stdio.h>

void move (int, char, char, char);

int main()

{

int n;

printf("\n Enter the number of rings: ");

scanf("%d", &n);

move (n, 'A', 'C', 'B');

return 0;

}

void move (int n, char source, char dest, char (spare)

{

if (n==1)

printf("\n Move from %c to %c", source, dest);

else

{

move (n-1, source, spare, dest);

move (1, source, dest, spare);

move (n-1, spare, dest, source);

}

}

Let us look at the Tower of Hanoi problem in detail using the program given above. Figure 4.16 explains the working of the program using one, then two, and finally three rings.