C Program to Find GCD Using Recursion

In this tutorial, we’ll create a C program to find the Greatest Common Divisor (GCD) of two numbers using recursion. GCD is the largest positive integer that divides each of the numbers without leaving a remainder. We’ll employ a recursive algorithm to calculate the GCD efficiently. Let’s dive into the details of the algorithm and the C code.

GCD Calculation Algorithm

1. Base Case: If $b$ is 0, return $a$ (base case for GCD).
2. Recursive Call: If $b$ is not 0, recursively call the GCD function with $b$ and $a\%b$.

C Program for Finding GCD Using Recursion

#include <stdio.h>

// Function to find GCD using recursion
int gcd(int a, int b) {
    // Base case
    if (b == 0) {
        return a;
    } else {
        // Recursive call
        return gcd(b, a % b);
    }
}

int main() {
    int num1, num2;

    // Input from user
    printf("Enter two positive integers: ");
    scanf("%d %d", &num1, &num2);

    // Check if the inputs are positive
    if (num1 <= 0 || num2 <= 0) {
        printf("Please enter positive integers.\n");
    } else {
        // Compute and display GCD
        printf("GCD of %d and %d = %d\n", num1, num2, gcd(num1, num2));
    }

    return 0;
}

Output Example

Example 1: Positive Integers

Enter two positive integers: 48 18
GCD of 48 and 18 = 6

Example 2: Zero

Enter two positive integers: 35 0
GCD of 35 and 0 = 35

Example 3: Negative Integers

Enter two positive integers: -15 20
Please enter positive integers.

Explanation

1. GCD Function: The gcd function is defined to calculate the GCD of two positive integers using recursion.
2. Base Case: The base case checks if the second number ($b$) is 0, in which case the GCD is the first number ($a$).
3. Recursive Call: If $b$ is not 0, the function recursively calls itself with $b$ and $a\%b$.

Conclusion

This C program efficiently computes the GCD of two positive integers using a recursive approach. The recursive nature of the algorithm allows for an elegant solution to the GCD calculation.

Feel free to experiment with different pairs of positive integers and observe how the GCD is computed. Understanding recursion is essential for implementing various algorithms efficiently.

If you have any questions or need further clarification, please don’t hesitate to ask!