The Tower of Hanoi is a classic problem in computer science and mathematics that demonstrates recursion. It involves moving a stack of disks from one peg to another, following specific rules. The problem consists of three pegs and a number of disks of different sizes that can slide onto any peg. The challenge is to move the entire stack to another peg, adhering to the following rules:

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

Recursive Approach to the Tower of Hanoi

The recursive approach to solving the Tower of Hanoi problem involves the following steps:

1. Move the top $n - 1$ disks from the source peg to the auxiliary peg.
2. Move the nth disk from the source peg to the destination peg.
3. Move the $n - 1$ disks from the auxiliary peg to the destination peg.

Implementation of Tower of Hanoi in C

Here's a simple implementation of the Tower of Hanoi program in C:

#include <stdio.h>

// Function to perform Tower of Hanoi
void towerOfHanoi(int n, char source, char destination, char auxiliary) {
    // Base case: If there is only one disk, simply move it from source to destination
    if (n == 1) {
        printf("Move disk 1 from %c to %c\n", source, destination);
        return;
    }
    
    // Move n-1 disks from source to auxiliary, using destination as auxiliary
    towerOfHanoi(n - 1, source, auxiliary, destination);
    
    // Move the nth disk from source to destination
    printf("Move disk %d from %c to %c\n", n, source, destination);
    
    // Move the n-1 disks from auxiliary to destination, using source as auxiliary
    towerOfHanoi(n - 1, auxiliary, destination, source);
}

int main() {
    int numDisks;

    // Prompt the user for the number of disks
    printf("Enter the number of disks: ");
    scanf("%d", &numDisks);

    // Call the towerOfHanoi function
    towerOfHanoi(numDisks, 'A', 'C', 'B'); // A = Source, C = Destination, B = Auxiliary

    return 0;
}

Explanation of the Program

1. Header Files:

   • #include <stdio.h>: This header file is included for standard input and output functions.

2. Function Declaration:

   • void towerOfHanoi(int n, char source, char destination, char auxiliary): This function takes the number of disks (n) and the names of the source, destination, and auxiliary pegs as arguments.

3. Base Case:

   • The base case checks if there is only one disk (n == 1). If so, it moves that disk from the source peg to the destination peg and returns.

4. Recursive Steps:

   • The function first moves $n - 1$ disks from the source peg to the auxiliary peg using the destination peg as an intermediary.
   • Next, it moves the nth disk from the source peg to the destination peg.
   • Finally, it moves the $n - 1$ disks from the auxiliary peg to the destination peg, using the source peg as an auxiliary.

5. Main Function:

   • The program starts by prompting the user to enter the number of disks.
   • It uses scanf() to read the input value.

6. Calling the Function:

   • The towerOfHanoi() function is called with the user-defined number of disks and the names of the pegs (A for source, C for destination, and B for auxiliary).

How to Run the Program

1. Compile the Code: Use a C compiler like gcc to compile the code.

   gcc tower_of_hanoi.c -o tower_of_hanoi
   

2. Execute the Program:

   ./tower_of_hanoi
   

3. Input Data: Enter the number of disks when prompted.

Example Input/Output

Input:

Enter the number of disks: 3

Output:

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

Conclusion

The Tower of Hanoi program in C illustrates the use of recursion to solve a classic problem. It effectively demonstrates how a complex problem can be broken down into simpler subproblems, each of which can be solved using the same approach. This recursive technique is a fundamental concept in computer science and is widely applicable to various problems.