Tower of Hanoi (TOH) Using Recursion
The Tower of Hanoi is a classic problem in computer science that demonstrates the power of recursion and the divide and conquer approach. It is widely used to understand how complex problems can be broken into smaller subproblems and solved systematically.
The problem consists of:
Three pegs:
- Source (A)
- Auxiliary (B)
- Destination (C)
N disks:
- All disks are of different sizes
- Initially stacked on peg A
- Arranged in decreasing order (largest at bottom, smallest at top)
Objective and Rules
The goal is to move all disks from peg A to peg C while following strict rules:
- Rule 1: Only one disk can be moved at a time
- Rule 2: A larger disk cannot be placed on a smaller disk
- Rule 3: Only the top disk of a peg can be moved
These constraints make the problem ideal for recursive thinking.
Understanding the Recursive Approach
The Tower of Hanoi problem can be solved by breaking it into smaller subproblems:
- Move (N − 1) disks from source (A) to auxiliary (B)
- Move the Nth (largest) disk from source (A) to destination (C)
- Move (N − 1) disks from auxiliary (B) to destination (C)
Key Idea
- The same process is repeated recursively for smaller values of N.
- Eventually, the problem reduces to moving a single disk (base case).
Step-by-Step Example (N = 3)
| Step | Move Disk | From Peg | To Peg |
|---|---|---|---|
| 1 | 1 | A | C |
| 2 | 2 | A | B |
| 3 | 1 | C | B |
| 4 | 3 | A | C |
| 5 | 1 | B | A |
| 6 | 2 | B | C |
| 7 | 1 | A | C |
Total moves = 7
Mathematical Formula
The minimum number of moves required to solve the problem is: T(N) = 2N − 1
Values for Different N
| N (Disks) | Minimum Moves |
|---|---|
| 1 | 1 |
| 2 | 3 |
| 3 | 7 |
| 4 | 15 |
| 5 | 31 |
The number of moves increases exponentially as N increases.
Complexity Analysis
Time Complexity
- The recurrence relation is:
T(N) = 2T(N − 1) + 1 - Time Complexity = O(2N)
- This means the algorithm becomes very slow for large N
Space Complexity
- Recursion uses stack memory
- Maximum recursive depth = N
- Space Complexity = O(N)
Real-World Applications
Although it is a theoretical puzzle, its concepts are used in:
Algorithm Design : Understanding recursion and divide & conquer
Data Structures : Stack operations and recursion
Artificial Intelligence : Problem decomposition
Robotics : Task planning and sequencing
File Systems : Recursive directory traversal
Tower of Hanoi Implementation in C
#include <stdio.h>
// Recursive function to solve Tower of Hanoi
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;
}
// Step 1: Move n-1 disks to auxiliary
towerOfHanoi(n - 1, source, destination, auxiliary);
// Step 2: Move nth disk to destination
printf("Move disk %d from %c to %c\n", n, source, destination);
// Step 3: Move n-1 disks to destination
towerOfHanoi(n - 1, auxiliary, source, destination);
}
int main() {
int n = 3;
printf("Steps to solve Tower of Hanoi for %d disks:\n", n);
towerOfHanoi(n, 'A', 'B', 'C');
return 0;
}Output for N = 3
Steps to solve Tower of Hanoi for 3 disks:
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 CConclusion
The Tower of Hanoi is an excellent example of recursion because it clearly demonstrates how a complex problem can be solved by dividing it into smaller subproblems.
- It follows the divide and conquer strategy
- It highlights the importance of:
- Base case
- Recursive breakdown
- Despite its exponential time complexity, it is a fundamental problem for understanding recursion
It is widely used as a teaching tool in algorithm design and problem-solving.
Was this article helpful?