The Tower of Hanoi Problem using Recursion
Suppose three pegs, labeled x, y and z are given and suppose on peg x there are placed a finite number n of disks with decreasing size. The object of the game is to move the disks from peg x to peg z using peg y as an auxiliary. The rules of the game are as follows:
1. Only one disk may be moved at a time.
2. Only the top disk on any peg may be moved to any other peg.
3. A larger disk can not be placed on a smaller disk.
Sometimes we will write x to y to denote the instruction "Move top disk from peg x to peg y." where x and y may be any of the three pegs.
The solution to the tower of Hanoi problem for n=3. Observe that it consist of the following seven moves:
n=3: Move top disk from peg x to peg z
Move top disk from peg x to peg y
Move top disk from peg z to peg y
Move top disk from peg x to peg z
Move top disk from peg y to peg x
Move top disk from peg y to peg z
Move top disk from peg x to peg z
Write a program to input n disks in a peg and find the movement by using recursion.
#include<stdio.h>
void tower(char, char, char, int);
void tower(char peg1, char peg2, char peg3, int n)
{
if(n<=0)
printf("\n Illegal Entry");
if(n==1)
printf("\n Move disk from %c to %c", peg1, peg3);
else
{
tower (peg1, peg3, peg2, n-1);
tower (peg1, peg2, peg3, 1);
tower (peg2, peg1, peg3, n-1);
}
}
void main()
{
int n;
clrscr();
printf ("\nInput the number of discs:");
scanf("%d",&n);
printf("\nTower of Hanoi for %d DISC",n);
tower('x','y','z',n);
}