Page 176 - DCAP407_DATA_STRUCTURE

Unit 9: Recursion

The initial set up of the Tower of Hanoi problem is depicted in figure 9.4. Let us analyze the set up.

Figure 9.4: Initial Set up of Tower of Hanoi

Once all the discs are transferred from ‘A’ to ‘C’, we get the setup as shown in Figure 9.5.
Figure 9.5: Set up of Tower of Hanoi After
Transferring Discs

To transfer ‘n’ discs from ‘A’ to ‘C’, the recursive method comprises three steps:
1. Transfer (n-1) discs from ‘A’ to ‘B’.
2. Transfer n disc from ‘A’ to ‘C’.
th
3. Transfer (n-1) discs from ‘B’ to ‘C’.
Program that computes the Tower of Hanoi using recursion.

/* A preprocessor directive to include functions related to user interfaces
*/
# include <conio.h>
/* A preprocessor directive to include functions related to standard
input and output operations */
# include <stdio.h>

/* Hanoi function is defined globally which holds four arguments and
does not return any value */
void Hanoi (int, char, char, char);
/* Main function */
main ()
{
/* Declare an integer variable n */
int n;
printf (“\n Input the number of discs:”);
/* Accept the integer value n */
scanf (“%d”, &n);
/* Hanoi function is invoked */

LOVELY PROFESSIONAL UNIVERSITY 169