Q:

Write a C program to perform Tower of Hanoi Algorithm using Recursion

Write a C program to perform Tower of Hanoi Algorithm using Recursion. Here’s a Simple Program to perform Tower of Hanoi Algorithm using Recursion in C Programming Language.

Tower of Hanoi

• The Tower of Hanoi (also called the Tower of Brahma or Lucas’ Tower and sometimes pluralized) is a mathematical game or puzzle. It consists of three rods, and a number of disks of different sizes which can slide onto any rod.
• The puzzle starts with the disks in a neat stack in ascending order of size on one rod, the smallest at the top, thus making a conical shape.

Rules : :

• Only one disk can be moved at a time.
• Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack i.e. a disk can only be moved if it is the uppermost disk on a stack.
• No disk may be placed on top of a smaller disk.

Algorithm  : :

The Tower of Hanoi Formula and the Steps For Moving N Disks from Source Tower to Destination Tower:

1. Move N-1 Disks from Source Tower To Temporary Tower
2. Move Nth Disk from Source Tower To Destination Tower
3. Move N-1 Disks from Temporary Tower To Destination Tower (using Source Tower as Temporary Tower)

For a total of n disks, 2n – 1 moves or disk shift are required.

Below is the source code for C program to perform Tower of Hanoi Algorithm using Recursion which is successfully compiled and run on Windows System to produce desired output as shown below :

SOURCE CODE : :

``````/* C program to perform Tower of Hanoi Algorithm using Recursion */

#include<stdio.h>
void hanoi_tower(char,char,char,int);
void hanoi_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
{
hanoi_tower(peg1,peg3,peg2,n-1);
hanoi_tower(peg1,peg2,peg3,1);
hanoi_tower(peg2,peg1,peg3,n-1);
}
}
void main ()
{
int n;
printf("\n Input the number of disc : ");
scanf("%d", &n);
printf("\n Tower of Hanoi for %d DISC :: \n", n);
hanoi_tower('x','y','z',n);
}``````

OUTPUT : :

```Input the number of disc : 4

Tower of Hanoi for 4 DISC ::

Move disk from x to y
Move disk from x to z
Move disk from y to z
Move disk from x to y
Move disk from z to x
Move disk from z to y
Move disk from x to y
Move disk from x to z
Move disk from y to z
Move disk from y to x
Move disk from z to x
Move disk from y to z
Move disk from x to y
Move disk from x to z
Move disk from y to z```