The "GCD Using Recursion" program in C calculates the Greatest Common Divisor (GCD) of two integers using a recursive approach. The GCD of two numbers is the largest positive integer that divides both numbers without leaving a remainder.

Recursive Approach to GCD

The GCD can be calculated using the Euclidean algorithm, which is based on the following principles:

1. If $b = 0$, then $\text{GCD}(a, b) = a$.
2. Otherwise, $\text{GCD}(a, b) = \text{GCD}(b, a \mod b)$.

Implementation of GCD Using Recursion

Here's a simple implementation of the GCD program using recursion in C:

#include <stdio.h>

// Function to calculate GCD recursively
int gcd(int a, int b) {
    // Base case: if b is 0, return a
    if (b == 0) {
        return a;
    }
    // Recursive case: call the function with b and a mod b
    return gcd(b, a % b);
}

int main() {
    int num1, num2, result;

    // Prompt the user for input
    printf("Enter two numbers: ");
    scanf("%d %d", &num1, &num2);

    // Call the recursive function and store the result
    result = gcd(num1, num2);

    // Print the result
    printf("GCD of %d and %d is: %d\n", num1, num2, result);

    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:

   • int gcd(int a, int b): This function takes two integers, a and b, and returns their GCD.

3. Base Case:

   • The base case checks if b is 0. If it is, the function returns a, as per the definition of GCD.

4. Recursive Case:

   • If b is not 0, the function calls itself with b and a % b as arguments. This process continues until b becomes 0.

5. Main Function:

   • The program starts by prompting the user to enter two integers.
   • It uses scanf() to read the input values.

6. Calling the Function:

   • The gcd() function is called with the input numbers, and the result is stored in the result variable.

7. Output:

   • The program prints the GCD of the entered numbers.

How to Run the Program

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

   gcc gcd_recursive.c -o gcd_recursive
   

2. Execute the Program:

   ./gcd_recursive
   

3. Input Data: Enter two integers when prompted.

Example Input/Output

Input:

Enter two numbers: 56 98

Output:

GCD of 56 and 98 is: 14

Conclusion

The "GCD Using Recursion" program in C illustrates the use of recursion to compute the greatest common divisor of two numbers. This method is efficient and concise, making it a preferred technique for solving problems that can be defined recursively. The Euclidean algorithm is particularly effective for calculating GCD, demonstrating the power of recursive functions in mathematical computations.