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

need an explanation for this answer? contact us directly to get an explanation for this answer

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

need an explanation for this answer? contact us directly to get an explanation for this answer