Tower of Hanoi

#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

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:

• 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.

---

2. Header Files Used

1. #include <iostream>
   • Provides cout and cin for input/output operations.

---

3. 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

---

4. 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

---

5. Base Case

Single Disk:

if (n == 1) { cout << "Move disk 1 from " << from << " to " << to << endl; return; }

How it works:

• Simplest case: one disk
• Direct move: source to destination
• Stops recursion
• Base of recursive tree

---

6. 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

---

7. 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!)

---

8. 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

---

9. 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

---

10. 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

---

11. return 0;

This ends the program successfully.

---

Summary

• Tower of Hanoi: move n disks from source to destination using auxiliary rod.
• Algorithm: move n-1 to auxiliary, move largest to destination, move n-1 to destination.
• Time complexity: O(2^n), minimum moves: 2^n - 1.
• Classic divide-and-conquer recursion example.
• Understanding Tower of Hanoi demonstrates recursive problem-solving.
• Essential for learning recursion and divide-and-conquer strategies.

This program is fundamental for learning advanced recursion, understanding divide-and-conquer, and preparing for complex recursive algorithms in C++ programs.