Tower of Hanoi in C++
Tower of Hanoi Problem using Recursion in C++.
IntermediateRecursion ProgramsExample 3 of 5
tower-of-hanoi.cpp
1#include <iostream>2using namespace std;34void towerOfHanoi(int n, char from, char to, char aux) {5 // Base case6 if (n == 1) {7 cout << "Move disk 1 from " << from << " to " << to << endl;8 return;9 }1011 // Move n-1 disks from 'from' to 'aux' using 'to' as auxiliary12 towerOfHanoi(n - 1, from, aux, to);1314 // Move the largest disk from 'from' to 'to'15 cout << "Move disk " << n << " from " << from << " to " << to << endl;1617 // Move n-1 disks from 'aux' to 'to' using 'from' as auxiliary18 towerOfHanoi(n - 1, aux, to, from);19}2021int main() {22 int n;23 cout << "Enter number of disks: ";24 cin >> n;2526 cout << "\nTower of Hanoi solution:" << endl;27 cout << "Moving " << n << " disks from A to C using B as auxiliary\n" << endl;2829 towerOfHanoi(n, 'A', 'C', 'B');3031 // Calculate total moves32 int totalMoves = (1 << n) - 1; // 2^n - 133 cout << "\nTotal moves required: " << totalMoves << endl;3435 return 0;36}
Output
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
What's going on
The program demonstrates Tower of Hanoi solution:
Recursive algorithm for moving disks
Divide-and-conquer approach
Moving disks between three rods
Calculating minimum moves required
Tower of Hanoi showcases elegant recursive problem-solving.
Header Files Used
1.#include <iostream>
Provides cout and cin for input/output operations.
Understanding Tower of Hanoi
Problem Statement
:
Three rods: source, destination, auxiliary
n disks of different sizes
Move all disks from source to destination
Rules: only move one disk at a time, larger disk cannot be on smaller
Goal
:
Move all disks to destination
Using minimum moves
Following the rules
Recursive Algorithm
Divide-and-Conquer Strategy
:
1.Move n-1 disks from source to auxiliary
2.Move largest disk from source to destination
3.Move n-1 disks from auxiliary to destination
How it works
:
Breaks problem into smaller subproblems
Recursively solves subproblems
Combines solutions
Classic divide-and-conquer
Base Case
Single Disk
:
if (n == 1) {
}
1cout << "Move disk 1 from " << from << " to " << to << endl;2return;
How it works
:
Simplest case: one disk
Direct move: source to destination
Stops recursion
Base of recursive tree
Recursive Case
Three Steps
:
1.towerOfHanoi(n-1, from, aux, to); // Move n-1 to auxiliary
2.Move largest disk to destination
3.towerOfHanoi(n-1, aux, to, from); // Move n-1 to destination
How it works
:
Recursively move n-1 disks
Move largest disk
Recursively move n-1 disks again
Each call reduces problem size
Minimum Moves
Formula
:
Total moves = 2^n - 1
How it works
:
Exponential growth
For n=3: 2^3 - 1 = 7 moves
For n=4: 2^4 - 1 = 15 moves
For n=64: 2^64 - 1 moves (legendary!)
Time Complexity
Analysis
:
Time: O(2^n) - exponential
Each disk requires recursive calls
Exponential growth with n
Efficient algorithm but exponential time
Space Complexity
:
O(n) - recursion depth
Stack frames for each level
Linear space usage
Depends on recursion depth
When to Use This Algorithm
Best For
:
Learning recursion
Understanding divide-and-conquer
Educational purposes
Small number of disks
Not Practical For
:
Large number of disks
Real-time applications
Performance-critical code
Production systems
Important Considerations
Recursive Structure
:
Classic divide-and-conquer
Breaks problem into subproblems
Elegant solution
Demonstrates recursion power
Exponential Growth
:
Moves grow exponentially
Large n becomes impractical
Legendary 64-disk problem
Demonstrates algorithm limits
Problem-Solving
:
Teaches recursive thinking
Divide-and-conquer strategy
Breaking complex into simple
Foundation for algorithms
return 0;
This ends the program successfully.