Tower of Hanoi (TOH)

Published by: Anil K. Panta

The Tower of Hanoi is a famous puzzle in computer science and mathematics that helps you understand the concept of recursion in a very visual and logical way.

What is the Tower of Hanoi

You have:

Three rods: A, B, and C
N disks of different sizes stacked on rod A in decreasing order (largest at bottom)

Goal:

Move all disks from rod A to rod C, following these 3 simple rules:

Only one disk can be moved at a time
Only the topmost disk can be moved
You cannot place a larger disk on top of a smaller one

Example for N = 3 (3 disks)

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

Algorithm: Tower of Hanoi Using Recursion

Step 1: If there is only 1 disk → move it directly from source to destination

Step 2: To move N disks:

a. Move top N-1 disks from 'A' to 'B' (using 'C')

b. Move the largest disk (N) from 'A' to 'C'

c. Move N-1 disks from 'B' to 'C' (using 'A')

Step 3: Repeat until all disks are moved to the destination rod

C Program: Tower of Hanoi Using Recursion

#include <stdio.h>

void towerOfHanoi(int n, char from_rod, char to_rod, char aux_rod) {

if (n == 0) {

return; // Base case: no disks to move

}

// Move n-1 disks from source to auxiliary rod

towerOfHanoi(n - 1, from_rod, aux_rod, to_rod);

// Move the remaining disk to destination

printf("Move disk %d from rod %c to rod %c\n", n, from_rod, to_rod);

// Move n-1 disks from auxiliary to destination rod

towerOfHanoi(n - 1, aux_rod, to_rod, from_rod);

}

int main() {

int N = 3;

// A, B and C are names of rods

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

Time and Space Complexity

Metric

Value

Time Complexity

O(2ⁿ)

Space Complexity

O(n)

There are 2ⁿ – 1 total moves
Each recursive call adds to the call stack, using memory

Summary:

Concept	Explanation
Puzzle Name	Tower of Hanoi
Method Used	Recursion
Number of Rods	3 (A, B, C)
Number of Moves	2ⁿ – 1 (for N disks)
Real Use	Learning recursion, problem-solving, stack operations
Key Idea	Break down the problem: move N–1 disks, then the last disk
Rules	Only move one disk at a time, and never put big over small

Final Thought:

The Tower of Hanoi puzzle is a classic problem that shows how complex tasks can be solved by dividing them into smaller problems — this is the true power of recursion.