Tower of Hanoi (TOH) using Recursion

The Tower of Hanoi is a classic recursion problem that involves moving a set of disks from one peg to another while following certain rules.

It is an excellent example of recursive problem-solving and divide and conquer approach.

The Tower of Hanoi puzzle consists of:

Three pegs (A, B, and C)
N disks of different sizes, stacked in decreasing order (largest at the bottom, smallest at the top) on peg A.

Objective or Rules of Tower of Honoi

Move all the disks from peg A to peg C, following these rules:

Rule 1: Only one disk can be moved at a time.
Rule 2: A disk can only be placed on an empty peg or on a larger disk.
Rule 3: A disk must be moved only from the top of a stack.

Understanding the Recursion Approach

To solve the Tower of Hanoi for N disks, we use the following recursive strategy:

Move (N-1) disks from peg A to peg B, using peg C as an auxiliary peg.
Move the largest disk (Nth disk) from peg A to peg C.
Move (N-1) disks from peg B to peg C, using peg A as an auxiliary peg.

This recursive breakdown forms a divide and conquer approach.

Step-by-Step Example (N = 3)

Let's take 3 disks (N = 3) and see how the recursion unfolds:

Step	Move Disk	From Peg	To Peg
1	Move Disk 1	A	C
2	Move Disk 2	A	B
3	Move Disk 1	C	B
4	Move Disk 3	A	C
5	Move Disk 1	B	A
6	Move Disk 2	B	C
7	Move Disk 1	A	C

Total Moves = 2^N−1 For N = 3, moves = 2³−1 = 7.

Mathematical Formula

The minimum number of moves required to solve the Tower of Hanoi for N disks is:

T(N) =2^N−1

For different values of N:

N (Disks)	Minimum Moves (2^N−1)
1	1
2	3
3	7
4	15
5	31

The number of moves grows exponentially.

Complexity Analysis

Time Complexity:

The recurrence relation for Tower of Hanoi is: T(N)=2T(N−1)+1

Solving this recurrence, we get: T(N)=O(2^N)

Space Complexity:

The recursive function stores N function calls in the stack at worst.
Space Complexity = O(N).

Real-World Applications

Although Tower of Hanoi is a mathematical puzzle, its concept is used in:

Data Structure Algorithms – Recursive problem-solving.
Computer Science – Stack operations and backtracking.
AI and Machine Learning – Problem decomposition.
Robotics – Planning and scheduling tasks.
File System Management – Recursive organization of directories.

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;
    }

    // Move (n-1) disks from source to auxiliary peg
    towerOfHanoi(n - 1, source, destination, auxiliary);

    // Move nth disk from source to destination
    printf("Move disk %d from %c to %c\n", n, source, destination);

    // Move (n-1) disks from auxiliary to destination peg
    towerOfHanoi(n - 1, auxiliary, source, destination);
}

int main() {
    int n = 3; // Number of disks
    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 C

The Tower of Hanoi is an excellent example of recursion and divide and conquer strategy. Despite its exponential time complexity, it serves as an essential learning tool in algorithm design.

Menu