Puzzle Rules & Recursive Strategy

The Tower of Hanoi is a mathematical puzzle with three rods ($A, B, C$) and n disks of different sizes.

• Rule 1: Only one disk can be moved at a time.
• Rule 2: Each move consists of taking the upper disk from one of the stacks and placing it on top of another stack.
• Rule 3: No disk may be placed on top of a smaller disk.

Recursive Insight:

1. Move $(n-1)$ disks from Source (A) to Auxiliary (B) using Destination (C).
2. Move the n-th disk from Source (A) to Destination (C).
3. Move $(n-1)$ disks from Auxiliary (B) to Destination (C) using Source (A).

---

C Source Code

c (ISO Standard)
Run in Compiler.cCopy
#include <stdio.h>

void towerOfHanoi(int n, char fromRod, char toRod, char auxRod) {
    if (n == 0) {
        return;
    }
    
    /* Step 1: Move top n-1 disks from source to auxiliary */
    towerOfHanoi(n - 1, fromRod, auxRod, toRod);
    
    /* Step 2: Move the nth disk to destination */
    printf("Move disk %d from rod %c -> rod %c\n", n, fromRod, toRod);
    
    /* Step 3: Move n-1 disks from auxiliary to destination */
    towerOfHanoi(n - 1, auxRod, toRod, fromRod);
}

int main() {
    int disks = 3;
    printf("Tower of Hanoi moves for %d disks:\n\n", disks);
    towerOfHanoi(disks, 'A', 'C', 'B');
    return 0;
}

Sample Output

text (ISO Standard)
Copy
Tower of Hanoi moves for 3 disks:

Move disk 1 from rod A -> rod C
Move disk 2 from rod A -> rod B
Move disk 1 from rod C -> rod B
Move disk 3 from rod A -> rod C
Move disk 1 from rod B -> rod A
Move disk 2 from rod B -> rod C
Move disk 1 from rod A -> rod C

---

Complexity Analysis

• Total Moves: $2^n - 1$ moves.
• Time Complexity: O(2ⁿ) exponential time.
• Space Complexity: O(n) recursion call stack depth.

---

Related Programs

• Practice recursive math in Fibonacci Series in C.
• Master function recursion in Functions in C Programming.