C Program to Find GCD Using Recursion

In mathematics, Greatest Common Divisor (GCD), also known as Highest Common Factor (HCF), of two or more integers is the largest possible integer that divides all the numbers without any reminder. To find out GCD at least one of the integers has to be no-zero. Here we’ll see how to white a recursive function to find out GCD of two integers, then we’ll apply this function for more than two integers.

C Program to Compute GCD:

int gcd(int a, int b)
{
    while (a != b)
    {
        if (a > b)
        {
            return gcd(a - b, b);
        }
        else
        {
            return gcd(a, b - a);
        }
    }
    return a;
}

Here is another version of the function which is better in terms of efficiency and number of lines of code.

int gcd(int a, int b)
{
    if (b == 0) return a;

    return gcd(b, a % b);
}

Here is complete program with main() function:

#include <stdio.h>
int gcd(int a, int b)
{
    if (b == 0) return a;

    return gcd(b, a % b);
}

void main()
{
    int a, b, result;

    printf("Enter the two numbers to find their GCD: ");
    scanf("%d%d", &a, &b);
    result = gcd(a, b);
    printf("The GCD of %d and %d is %d.\n", a, b, result);

}

Output of the program:

Output of GCD program

Now we’ll see how to use the above function to calculate GCD for more than two integers. If you have an array of integers and you want to find GCD for all the integers of the array the code will look like.

int arr[10] = {15, 35, 55, 555, 65, 945, 25, 875, 45, 705};
int result = 0;

result = arr[0];

for (i = 1; i < 10; i++)
{
    result = gcd(result, arr[i]);
}

Here first we assume that first element of the array is the GCD (set as result). The we call the gcd() function with the result and the second element. The return value is set to result. Then we call the gcd() function again with the result and the third element. We continue this process for rest of the elements of the array. The final result will become the GCD for all elements of the array.