C Program to Solve the Tower of Hanoi Problem Using Recursion

Introduction

The Tower of Hanoi is a classic problem in mathematics and computer science that involves moving a set of disks from one rod to another, following specific rules:

1. Only one disk can be moved at a time.
2. A disk can only be placed on top of a larger disk.
3. All disks must be moved from the source rod to the destination rod using an auxiliary rod.

Example:

• Input: 3 disks
• Output: Sequence of moves to solve the problem.

Problem Statement

Create a C program that:

• Takes the number of disks as input from the user.
• Uses a recursive function to print the sequence of moves required to solve the Tower of Hanoi problem.

Solution Steps

1. Include the Standard Input-Output Library: Use #include <stdio.h> for standard input-output functions.
2. Write the Recursive Function: Define a recursive function that solves the Tower of Hanoi problem.
3. Write the Main Function: Define the main function to take user input and call the recursive function.
4. Input the Number of Disks: Use scanf to take input from the user for the number of disks.
5. Call the Recursive Function: Pass the number of disks and the names of the rods to the recursive function.
6. Display the Moves: The recursive function prints the sequence of moves required to solve the problem.

C Program to Solve the Tower of Hanoi Problem Using Recursion

#include <stdio.h>

// Step 2: Define the recursive function to solve the Tower of Hanoi problem
void towerOfHanoi(int n, char source, char destination, char auxiliary) {
    if (n == 1) {
        printf("Move disk 1 from rod %c to rod %c\n", source, destination);
        return;  // Base case: Only one disk to move
    }
    
    // Move top 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 rod %c to rod %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() {
    // Step 3: Declare a variable to hold the number of disks
    int n;

    // Step 4: Prompt the user to enter the number of disks
    printf("Enter the number of disks: ");
    scanf("%d", &n);

    // Step 5: Call the recursive function to solve the Tower of Hanoi problem
    towerOfHanoi(n, 'A', 'C', 'B');  // A = Source, C = Destination, B = Auxiliary

    return 0;  // Return 0 to indicate successful execution
}

Explanation

Step 2: Define the Recursive Function

• The towerOfHanoi function takes four parameters:
  • n: The number of disks to move.
  • source: The rod from which the disks are moved.
  • destination: The rod to which the disks are moved.
  • auxiliary: The auxiliary rod used during the process.
• Base Case: If there is only one disk, it is moved directly from the source to the destination.
• Recursive Case:
  • Move the top n-1 disks from the source to the auxiliary rod.
  • Move the nth disk from the source to the destination rod.
  • Move the n-1 disks from the auxiliary rod to the destination rod.

Step 3: Declare a Variable

• The variable n is declared to store the number of disks.

Step 4: Input the Number of Disks

• The program prompts the user to enter the number of disks using scanf.

Step 5: Call the Recursive Function

• The program calls the towerOfHanoi function with the number of disks and the names of the rods (A, C, B).

Return 0

• The return 0; statement indicates that the program executed successfully.

Output Example

Example 1 (3 Disks):

Enter the number of disks: 3
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

Example 2 (2 Disks):

Enter the number of disks: 2
Move disk 1 from rod A to rod B
Move disk 2 from rod A to rod C
Move disk 1 from rod B to rod C

Conclusion

This C program demonstrates how to solve the Tower of Hanoi problem using a recursive function. It covers basic concepts such as recursion, base cases, and problem-solving strategies, making it a useful example for beginners learning C programming.