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)


TOH( n,  Sour, Aux , Des)
    Write ("Move Disk “, n ," from ", Sour ," to ",Des)
    Write ("Move Disk “, n ," from ", Sour ," to ",Des)

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

using namespace std;

//tower of HANOI function implementation
void TOH(int n,char Sour, char Aux,char Des)
		cout<<"Move Disk "<<n<<" from "<<Sour<<" to "<<Des<<endl;
	cout<<"Move Disk "<<n<<" from "<<Sour<<" to "<<Des<<endl;

//main program
int main()
	int n;
	cout<<"Enter no. of disks:";	
	//calling the TOH 
	return 0;


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

Comments and Discussions

Languages: » C » C++ » C++ STL » Java » Data Structure » C#.Net » Android » Kotlin » SQL
Web Technologies: » PHP » Python » JavaScript » CSS » Ajax » Node.js » Web programming/HTML
Solved programs: » C » C++ » DS » Java » C#
Aptitude que. & ans.: » C » C++ » Java » DBMS
Interview que. & ans.: » C » Embedded C » Java » SEO » HR
CS Subjects: » CS Basics » O.S. » Networks » DBMS » Embedded Systems » Cloud Computing
» Machine learning » CS Organizations » Linux » DOS
More: » Articles » Puzzles » News/Updates

© https://www.includehelp.com some rights reserved.