C++ Program for Tower of Hanoi with Output and Explanation

A C++ program for Tower of Hanoi uses a recursive function like void towerOfHanoi(int n, char from, char to, char aux) to move disks between rods and prints each move with std::cout.

Examples

Inputn = 1

OutputMove disk 1 from rod A to rod C

Inputn = 2

OutputMove disk 1 from rod A to rod B Move disk 2 from rod A to rod C Move disk 1 from rod B to rod C

Inputn = 3

OutputMove disk 1 from rod A to rod C Move disk 2 from rod A to rod B Move disk 1 from rod C to rod B Move disk 3 from rod A to rod C Move disk 1 from rod B to rod A Move disk 2 from rod B to rod C Move disk 1 from rod A to rod C

How to Think About It

To solve Tower of Hanoi, think about moving the top n-1 disks to the auxiliary rod first, then move the largest disk to the target rod, and finally move the n-1 disks from the auxiliary rod to the target rod. This repeats recursively until only one disk is moved directly.

Algorithm

1

If there is only one disk, move it from the source rod to the target rod and return.

2

Recursively move n-1 disks from the source rod to the auxiliary rod.

3

Move the nth disk from the source rod to the target rod.

4

Recursively move the n-1 disks from the auxiliary rod to the target rod.

Code

cpp

#include <iostream>
void towerOfHanoi(int n, char from, char to, char aux) {
    if (n == 1) {
        std::cout << "Move disk 1 from rod " << from << " to rod " << to << "\n";
        return;
    }
    towerOfHanoi(n - 1, from, aux, to);
    std::cout << "Move disk " << n << " from rod " << from << " to rod " << to << "\n";
    towerOfHanoi(n - 1, aux, to, from);
}

int main() {
    int n = 3;
    towerOfHanoi(n, 'A', 'C', 'B');
    return 0;
}

Output

Move disk 1 from rod A to rod C
Move disk 2 from rod A to rod B
Move disk 1 from rod C to rod B
Move disk 3 from rod A to rod C
Move disk 1 from rod B to rod A
Move disk 2 from rod B to rod C
Move disk 1 from rod A to rod C

Dry Run

Let's trace the Tower of Hanoi program with n=2 disks moving from rod A to rod C using rod B as auxiliary.

1

Move n-1 disks from A to B

Call towerOfHanoi(1, 'A', 'B', 'C') which moves disk 1 from A to B.

2

Move nth disk from A to C

Move disk 2 from rod A to rod C.

3

Move n-1 disks from B to C

Call towerOfHanoi(1, 'B', 'C', 'A') which moves disk 1 from B to C.

Step	Action
1	Move disk 1 from A to B
2	Move disk 2 from A to C
3	Move disk 1 from B to C

Why This Works

Step 1: Base Case

When there is only one disk, the program moves it directly from the source rod to the target rod using std::cout.

Step 2: Recursive Calls

The program moves the top n-1 disks to the auxiliary rod, then moves the largest disk to the target rod, and finally moves the n-1 disks from auxiliary to target rod recursively.

Step 3: Print Moves

Each move is printed immediately, showing the disk number and the rods involved, which helps visualize the solution.

Alternative Approaches

Iterative Approach Using Stack

cpp

#include <iostream>
#include <stack>
#include <tuple>

void towerOfHanoiIterative(int n, char from, char to, char aux) {
    std::stack<std::tuple<int, char, char, char>> s;
    s.push(std::make_tuple(n, from, to, aux));
    while (!s.empty()) {
        auto [disks, src, dst, auxr] = s.top();
        s.pop();
        if (disks == 1) {
            std::cout << "Move disk 1 from rod " << src << " to rod " << dst << "\n";
        } else {
            s.push(std::make_tuple(disks - 1, auxr, dst, src));
            s.push(std::make_tuple(1, src, dst, auxr));
            s.push(std::make_tuple(disks - 1, src, auxr, dst));
        }
    }
}

int main() {
    int n = 3;
    towerOfHanoiIterative(n, 'A', 'C', 'B');
    return 0;
}

This uses a stack to simulate recursion, which can be useful if recursion depth is a concern, but the code is more complex and less intuitive.

Using Memoization to Store Moves

cpp

#include <iostream>
#include <vector>
#include <string>

std::vector<std::string> moves;

void towerOfHanoiMemo(int n, char from, char to, char aux) {
    if (n == 1) {
        moves.push_back("Move disk 1 from rod " + std::string(1, from) + " to rod " + std::string(1, to));
        return;
    }
    towerOfHanoiMemo(n - 1, from, aux, to);
    moves.push_back("Move disk " + std::to_string(n) + " from rod " + std::string(1, from) + " to rod " + std::string(1, to));
    towerOfHanoiMemo(n - 1, aux, to, from);
}

int main() {
    int n = 3;
    towerOfHanoiMemo(n, 'A', 'C', 'B');
    for (const auto& move : moves) {
        std::cout << move << "\n";
    }
    return 0;
}

This stores all moves in a vector before printing, which allows further processing or delayed output but uses extra memory.

Complexity: O(2^n) time, O(n) space

Time Complexity

The algorithm makes two recursive calls for n-1 disks plus one move, resulting in 2^n - 1 moves, so time complexity is exponential O(2^n).

Space Complexity

The recursion stack depth is n, so space complexity is O(n) due to function call stack usage.

Which Approach is Fastest?

Recursive approach is simplest and efficient for small n; iterative approach avoids recursion stack but is more complex; memoization uses extra memory but allows move storage.

Approach	Time	Space	Best For
Recursive	O(2^n)	O(n)	Simplicity and clarity
Iterative with Stack	O(2^n)	O(n)	Avoiding recursion stack overflow
Memoization	O(2^n)	O(2^n)	Storing moves for later use