Tower of Hanoi
Tower of Hanoi Problem using Recursion in C++
IntermediateTopic: Recursion Programs
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;
}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
Understanding Tower of Hanoi
Tower of Hanoi: Move n disks from source to destination using auxiliary rod. Algorithm: 1) Move n-1 disks to auxiliary, 2) Move largest disk to destination, 3) Move n-1 disks from auxiliary to destination. Time complexity: O(2^n). Minimum moves: 2^n - 1. Classic example of divide-and-conquer recursion.
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.