# 11.4 – Towers of Hanoi – Recursion

by on December 10, 2017

## Towers of Hanoi:

It is a mathematical puzzle, is also called tower of Brahma or Lucas tower. It consists of three pegs or rods and number of disks of different sizes which can slide onto any peg.
At the beginning of the game, all the plates are arranged in ascending order on peg A that is smallest on top and biggest on bottom.

The objective of this game is to move all disks from peg A to peg C using auxiliary peg B using some rules.

1. Only one disk must be moved at a time
2. Only top disk must be moved and placed only on top
3. A disk can’t be placed on small disk
4. Game must be completed within 2n-1 steps

Now let us play the game with two plates

Let us play the game with three plates now

It is difficult to play the game as the number of plates grows. The recursive solution to towers of Hanoi is

tower(beg,end,aux,n-1)
beg->end
tower(aux,beg,end,n-1)

Equivalent implementation in C language is

void tower(char beg,char aux,char end,int n)
{
if(n==0)
return;
tower(beg,end,aux,n-1);
printf("\n%c -> %c",beg,end);
tower(aux,beg,end,n-1);
}

Let us test it with 3 disks A, B and C

#include<stdio.h>
void tower(char,char,char,int);
int main()
{
int n;
printf("nEnter number of plates:");
scanf("%d",&n);
tower('A','B','C',n);
return 0;
}
void tower(char beg,char aux,char end,int n)
{
if(n==0)
return;
tower(beg,end,aux,n-1);
printf("\n%c -> %c",beg,end);
tower(aux,beg,end,n-1);
}

Execution:
Enter number of plates:2
A -> B
A -> C
B -> C

Execution:
Enter number of plates:3
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C