Tower Of Hanoi is a classic problem of Recursion. So this problem really gives you the insights of Recursion and how well it works in these problems.

Recursion is applied to problems that have the Optimal substructure property.

And the Tower of Hanoi problem also follows this property.

And the Tower of Hanoi problem also follows this property.

For Example,

**can be easily solved by**

*Moving n disks from A to C using B*

*Moving n-1 disks from A to B using C**+ Moving 1 disk from A to C +*

*Moving n-1 disks from B to C using A**.*

*Here you can see we are able to reduce the problem from*

*n*to

*n-1*,then

*n-1*will be reduce to

*n-2*and so on till we reach a case that is trivial for us to answer i.e.

*n=0*.

This trivial case is often called base case in recursion.

There are many applications of Recursion such as in Linked Lists,Trees,Graphs etc.

How to move n discs from Tower1 to Tower2 ?

1. Move n-1 discs from Tower1 to Tower 3

2. Move nth disc from Tower1 to Tower2

3. Move n-1 discs from Tower3 to Tower1

This is the recursion concept behind tower of hanoi.

In C, we may write (just printing the steps)

#include <stdio.h>

void towerofhanoi(int n,char src[],char dst[],char ext[]){

if(n>0){

towerofhanoi(n-1,src,ext,dst); \\moving n-1 discs from source to spare

move(n,src,dst);

towerofhanoi(n-1,ext,dst,src); \\moving n-1 discs back from spare to destination

}

}

void move(int n,char src[],char dst[]){

static int count = 0;

count++;

printf("%d: move %d from %s to %s\n",count,n,src,dst);

}

int main(){

int discs;

printf("\t\tTower of Hanoi\n\n");

printf("Enter the number of Discs: ");

scanf("%d",&discs);

towerofhanoi(3,"Tower1","Tower2","Tower3");

return 0;

}