Solving Tower of Hanoi Using Recursion in C

🧠 Solving the Tower of Hanoi Using Recursion in C

The Tower of Hanoi is a famous puzzle that beautifully demonstrates recursion. It involves three rods and a number of disks of different sizes that can slide onto any rod. The puzzle starts with all disks stacked in decreasing size on one rod (source rod).

🎯 Goal:

Move the entire stack to another rod, following these rules:

• Only one disk can be moved at a time.
• Each move involves taking the top disk from one rod and placing it on another.
• No larger disk may be placed on top of a smaller disk.

🧮 Recursive Solution Logic

To move n disks from Source to Destination using Auxiliary:

• Move n-1 disks from Source to Auxiliary.
• Move the largest disk (nth) from Source to Destination.
• Move the n-1 disks from Auxiliary to Destination.

💻 C Program to Solve Tower of Hanoi

#include <stdio.h>

void towerOfHanoi(int n, char source, char auxiliary, char destination) {
    if (n == 1) {
        printf("Move disk 1 from %c to %c\\n", source, destination);
        return;
    }

    towerOfHanoi(n - 1, source, destination, auxiliary);
    printf("Move disk %d from %c to %c\\n", n, source, destination);
    towerOfHanoi(n - 1, auxiliary, source, destination);
}

int main() {
    int n = 3; // Change this value to test different sizes
    towerOfHanoi(n, 'A', 'B', 'C');
    return 0;
}

📤 Sample Output (n = 3)

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

📌 Visual Summary of Steps (3 Disks)

• Step 1: Move 1 → A to C
• Step 2: Move 2 → A to B
• Step 3: Move 1 → C to B
• Step 4: Move 3 → A to C
• Step 5: Move 1 → B to A
• Step 6: Move 2 → B to C
• Step 7: Move 1 → A to C

🧠 How Many Moves Are Needed?

The number of moves required to solve the puzzle for n disks is:

Total moves = 2^n - 1

For 3 disks: 2³ - 1 = 7 moves

For 4 disks: 2⁴ - 1 = 15 moves

⚠️ Common Mistakes

• Forgetting the base case if (n == 1)
• Passing wrong order of rods (source, aux, dest)
• Trying to manually simulate instead of trusting the recursive logic

✅ Conclusion

The Tower of Hanoi is not just a puzzle—it's a fundamental exercise in understanding recursion. Once you understand how the pieces move with n-1 calls, recursion will feel like second nature. Try it for 4 or 5 disks and see how quickly the number of moves grows!