Home » Data Structure

Tower of Hanoi using recursion (C++ program)



Implementation of Tower of HANOI in using C++ program, Learn: What is Tower of Hanoi? How to implement using recursion in C++?
Submitted by Abhishek Jain, on July 23, 2017

The Tower of Hanoi is a mathematical puzzle invented by the French mathematician Edouard Lucas in 1883.

There are three pegs, source(A), Auxiliary (B) and Destination(C). Peg A contains a set of disks stacked to resemble a tower, with the largest disk at the bottom and the smallest disk at the top. figure 1 Illustrate the initial configuration of the pegs for 3 disks. The objective is to transfer the entire tower of disks in peg A to peg C maintaining the same order of the disks.

Obeying the following rules:

  1. Only one disk can be transfer at a time.
  2. Each move consists of taking the upper disk from one of the peg and placing it on the top of another peg i.e. a disk can only be moved if it is the uppermost disk of the peg.
  3. Never a larger disk is placed on a smaller disk during the transfer.
tower of HANOI implementation

(figure 1)



The solution to the puzzle calls for an application of recursive functions and recurrence relations.

A skeletal recursive procedure (Outline) for the solution of the problem for N number of disks is as follows:

  1. Move the top N-1 disks from peg A to peg B (using C as an auxiliarypeg)
  2. Move the bottom disk from peg A to peg C
  3. Move N-1 disks from Peg B to Peg C (using Peg A as an auxiliary peg)

The pictorial representation of the skeletal recursive procedure for N=4 disks is shown in Figure 2.

tower of HANOI implementation

(figure 2)



Algorithm

TOH( n,  Sour, Aux , Des)
If(n=1)
    Write ("Move Disk “, n ," from ", Sour ," to ",Des)
Else
    TOH(n-1,Sour,Des,Aux);
    Write ("Move Disk “, n ," from ", Sour ," to ",Des)
    TOH(n-1,Aux,Sour,Des);
END

Let’s take an example to better understand the algorithm (For n=3).

tower of HANOI implementation

(figure 3)



Implementation of Tower of HANOI in using C++ program

#include<iostream>
using namespace std;

//tower of HANOI function implementation
void TOH(int n,char Sour, char Aux,char Des)
{ 
	if(n==1)
	{
		cout<<"Move Disk "<<n<<" from "<<Sour<<" to "<<Des<<endl;
		return;
	}
	
	TOH(n-1,Sour,Des,Aux);
	cout<<"Move Disk "<<n<<" from "<<Sour<<" to "<<Des<<endl;
	TOH(n-1,Aux,Sour,Des);
}

//main program
int main()
{ 
	int n;
	
	cout<<"Enter no. of disks:";	
	cin>>n;
	//calling the TOH 
	TOH(n,'A','B','C');
	
	return 0;
}

Output

Enter no. of disks:3
Move Disk 1 from A to C
Move Disk 2 from A to B
Move Disk 1 from C to B
Move Disk 3 from A to C
Move Disk 1 from B to A
Move Disk 2 from B to C
Move Disk 1 from A to C

Image Reference:

  1. http://www.peterloos.de/index.php/m-wpf/m-wpf-userdefined-controls/59-a-wpf-towersofhanoi
  2. http://algorithms.tutorialhorizon.com/towers-of-hanoi/
  3. https://www.researchgate.net/publication/278658550_An_Evolutionary_Approach_to_Tower_of_Hanoi_Problem





Was this page helpful? Please share with your friends...

Are you a blogger? Join our Blogging forum.



Comments and Discussions





© https://www.includehelp.com (2015-2018), Some rights reserved.




close Like other websites, this site uses cookies to deliver relevant ads based on your interest, by using our website, you acknowledge that you have read our privacy policy.