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) that moves disks between rods by calling itself to solve smaller subproblems.

Examples

Input3

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

Input1

OutputMove disk 1 from rod A to rod C

Input0

Output

How to Think About It

To solve Tower of Hanoi, think about moving the top n-1 disks to an 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 uses the idea of breaking the problem into smaller similar problems using recursion.

Algorithm

1

If number of disks n is 0, return (no move needed).

2

Move n-1 disks from source rod to auxiliary rod using target rod.

3

Move the nth disk from source rod to target rod.

4

Move the n-1 disks from auxiliary rod to target rod using source rod.

Code

c

#include <stdio.h>

void towerOfHanoi(int n, char from, char to, char aux) {
    if (n == 0) return;
    towerOfHanoi(n - 1, from, aux, to);
    printf("Move disk %d from rod %c to rod %c\n", n, from, to);
    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 for 3 disks moving from rod A to rod C using rod B as auxiliary.

1

Move 2 disks from A to B

Call towerOfHanoi(2, A, B, C)

2

Move 1 disk from A to C

Call towerOfHanoi(1, A, C, B) and print 'Move disk 1 from rod A to rod C'

3

Move disk 2 from A to B

Print 'Move disk 2 from rod A to rod B'

4

Move 1 disk from C to B

Call towerOfHanoi(1, C, B, A) and print 'Move disk 1 from rod C to rod B'

5

Move disk 3 from A to C

Print 'Move disk 3 from rod A to rod C'

6

Move 2 disks from B to C

Call towerOfHanoi(2, B, C, A)

Step	Action
1	Move disk 1 from rod A to rod C
2	Move disk 2 from rod A to rod B
3	Move disk 1 from rod C to rod B
4	Move disk 3 from rod A to rod C
5	Move disk 1 from rod B to rod A
6	Move disk 2 from rod B to rod C
7	Move disk 1 from rod A to rod C

Why This Works

Step 1: Recursive Breakdown

The function calls itself with smaller numbers of disks, breaking the problem into moving n-1 disks first.

Step 2: Base Case

When n is 0, the function returns immediately, stopping recursion.

Step 3: Moving Largest Disk

After moving n-1 disks to auxiliary rod, the largest disk is moved directly to the target rod.

Step 4: Completing the Move

Finally, the n-1 disks are moved from auxiliary rod to target rod, completing the puzzle.

Alternative Approaches

Iterative Approach Using Stack

c

#include <stdio.h>
#include <stdlib.h>

// This approach simulates recursion using a stack but is more complex and less intuitive.
// It is not shown here due to complexity but can be implemented using explicit stack data structures.
int main() {
    printf("Iterative solution is complex and not shown here.\n");
    return 0;
}

Iterative solutions use explicit stacks to simulate recursion but are harder to understand and implement.

Using Bitwise Operations

c

#include <stdio.h>

void towerOfHanoi(int n, char from, char to, char aux) {
    if (n == 0) return;
    towerOfHanoi(n - 1, from, aux, to);
    printf("Move disk %d from rod %c to rod %c\n", n, from, to);
    towerOfHanoi(n - 1, aux, to, from);
}

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

Bitwise methods exist for iterative solutions but recursive method is clearer and preferred for learning.

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

Time Complexity

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

Space Complexity

The recursion stack grows up to n calls deep, so space complexity is O(n).

Which Approach is Fastest?

Recursive approach is simplest and clear but iterative methods can be more complex and less readable.

Approach	Time	Space	Best For
Recursive	O(2^n)	O(n)	Clarity and simplicity
Iterative with Stack	O(2^n)	O(n)	Avoid recursion but more complex
Bitwise Iterative	O(2^n)	O(1)	Optimized but hard to understand