C++ Program to Solve Tower of Hanoi using Recursion

Tower of Hanoi is a famous recursive problem which is based on 3 pegs and a set of the disc with different sizes.

Rules of Tower of Hanoi:

1. Only one disc can be moved at a time.
2. Only the top disc on any peg can be moved to any other peg.
3. A larger disc can’t be placed on a smaller peg.

Program:

#include
#include
using namespace std;
void TOH(int d, char t1, char t2, char t3)
{
if(d==1)
{
cout<<"\nShift top disk from tower"<<t1<<" to tower"<<t2;
return;
}
TOH(d-1,t1,t3,t2);
cout<<"\nShift top disk from tower"<<t1<<" to tower"<<t2;
TOH(d-1,t3,t2,t1);
}
int main()
{
int disk;
cout<<"Enter the number of disks:"; cin>>disk;
if(disk<1)
cout<<"There are no disks to shift";
else
cout<<"There are "<<disk<<"disks in tower 1\n";
TOH(disk, '1','2','3');
cout<<"\n\n"<<disk<<"disks in tower 1 are shifted to tower 2";
getch();
return 0;
}

Output:

Enter the number of disks: 3
There are 3 disks in tower 1
Shift top disk from tower 1 to tower 2
Shift top disk from tower 1 to tower 3
Shift top disk from tower 2 to tower 3
Shift top disk from tower 1 to tower 2
Shift top disk from tower 3 to tower 1
Shift top disk from tower 3 to tower 2
Shift top disk from tower 1 to tower 2
3 disks in tower 1 are shifted to tower 2