Tower of Hanoi
Tower of Hanoi Problem using Recursion in C++
C++ Tower of Hanoi Program
This program helps you to learn the fundamental structure and syntax of C++ programming.
#include <iostream>
using namespace std;
void towerOfHanoi(int n, char from, char to, char aux) {
// Base case
if (n == 1) {
cout << "Move disk 1 from " << from << " to " << to << endl;
return;
}
// Move n-1 disks from 'from' to 'aux' using 'to' as auxiliary
towerOfHanoi(n - 1, from, aux, to);
// Move the largest disk from 'from' to 'to'
cout << "Move disk " << n << " from " << from << " to " << to << endl;
// Move n-1 disks from 'aux' to 'to' using 'from' as auxiliary
towerOfHanoi(n - 1, aux, to, from);
}
int main() {
int n;
cout << "Enter number of disks: ";
cin >> n;
cout << "\nTower of Hanoi solution:" << endl;
cout << "Moving " << n << " disks from A to C using B as auxiliary\n" << endl;
towerOfHanoi(n, 'A', 'C', 'B');
// Calculate total moves
int totalMoves = (1 << n) - 1; // 2^n - 1
cout << "\nTotal moves required: " << totalMoves << endl;
return 0;
}Enter number of disks: 3 Tower of Hanoi solution: Moving 3 disks from A to C using B as auxiliary 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 Total moves required: 7
Understanding Tower of Hanoi
This program teaches you how to solve the Tower of Hanoi problem using Recursion in C++. The Tower of Hanoi is a classic mathematical puzzle and an excellent example of divide-and-conquer recursion. It demonstrates how complex problems can be elegantly solved by breaking them into smaller subproblems.
---
1. What This Program Does
The program demonstrates Tower of Hanoi solution:
Tower of Hanoi showcases elegant recursive problem-solving.
---
2. Header Files Used
---
3. Understanding Tower of Hanoi
Problem Statement
:
Goal
:
---
4. Recursive Algorithm
Divide-and-Conquer Strategy
:
How it works
:
---
5. Base Case
Single Disk
:
if (n == 1) {
}
cout << "Move disk 1 from " << from << " to " << to << endl;
return;How it works
:
---
6. Recursive Case
Three Steps
:
How it works
:
---
7. Minimum Moves
Formula
:
Total moves = 2^n - 1
How it works
:
---
8. Time Complexity
Analysis
:
Space Complexity
:
---
9. When to Use This Algorithm
Best For
:
Not Practical For
:
---
10. Important Considerations
Recursive Structure
:
Exponential Growth
:
Problem-Solving
:
---
11. return 0;
This ends the program successfully.
---
Summary
This program is fundamental for learning advanced recursion, understanding divide-and-conquer, and preparing for complex recursive algorithms in C++ programs.
Let us now understand every line and the components of the above program.
Note: To write and run C++ programs, you need to set up the local environment on your computer. Refer to the complete article Setting up C++ Development Environment. If you do not want to set up the local environment on your computer, you can also use online IDE to write and run your C++ programs.
Practical Learning Notes for Tower of Hanoi
This C++ program is part of the "Recursion Programs" topic and is designed to help you build real problem-solving confidence, not just memorize syntax. Start by understanding the goal of the program in plain language, then trace the logic line by line with a custom input of your own. Once you can predict the output before running the code, your understanding becomes much stronger.
A reliable practice pattern is to run the original version first, then modify only one condition or variable at a time. Observe how that single change affects control flow and output. This deliberate style helps you understand loops, conditions, and data movement much faster than copying full solutions repeatedly.
For interview preparation, explain this solution in three layers: the high-level approach, the step-by-step execution, and the time-space tradeoff. If you can teach these three layers clearly, you are ready to solve close variations of this problem under time pressure.