C Program To Find GCD of Two Numbers using Recursion: Euclid’s Algorithm

Lets write a C program to find GCD(Greatest Common Divisor) or HCF(Highest Common Factor) of two positive integer numbers input by the user using Euclid’s Algorithm and by using Recursive function call logic.

Related Read:
C Program To Find GCD and LCM of Two Numbers using Euclidean algorithm
Recursive Functions In C Programming Language

Euclid’s Algorithm Logic

If user inputs 2 numbers n1 and n2, reduce the bigger number by modulo dividing it by the smaller number. For example, if n1 is greater than n2, then reduce the value of n1 by replacing it with n1%n2.

Assume that we’ve a function gcd() which returns gcd of 2 numbers passed to it. Ex: gcd(n1, n2);

According to Euclid’s Algorithm, we’ll get the same gcd if we reduce the bigger number by modulo dividing it by smaller number.

If n1 > n2 we need to pass gcd(n1%n2, n2);
If n2 > n1, we need to pass gcd(n1, n2%n1);

We need to recursively execute above 2 lines of logic until either n1 is 0 or until n2 is 0. If n1 is 0, then value present in n2 is the gcd of (n1,n2). If n2 is 0, then value present in n1 is the gcd of (n1,n2).

Video Tutorial: C Program To Find GCD of Two Numbers using Recursion: Euclid’s Algorithm

Source Code: C Program To Find GCD of Two Numbers using Recursion: Euclid’s Algorithm

#include<stdio.h>

int gcd(int, int);

int main()
{
    int num1, num2;

    printf("Enter 2 positive integer numbers\n");
    scanf("%d%d", &num1, &num2);

    printf("\nGCD of %d and %d is %d.\n", num1, num2, gcd(num1, num2));

    return 0;
}

int gcd(int n1, int n2)
{
    if(n1 == 0) return n2;
    if(n2 == 0) return n1;

    if(n1 > n2)
        return gcd(n1%n2, n2);
    else
        return gcd(n1, n2%n1);
}

Output 1:
Enter 2 positive integer numbers
1980
1617

GCD of 1980 and 1617 is 33.

Output 2:
Enter 2 positive integer numbers
15
20

GCD of 15 and 20 is 5.

Example:

Lets assume that user has entered n1 = 1980 and n2 = 1617

In above table gcd(33, 0) gets called, since n2 = 0, our program returns value of n1 as gcd, which is 33.

So GCD of 1980 and 1617 is 33.

Source Code: C Program To Find GCD of Two Numbers using Recursion and Ternary or Conditional Operator: Euclid’s Algorithm

#include<stdio.h>

int gcd(int, int);

int main()
{
    int num1, num2;

    printf("Enter 2 positive integer numbers\n");
    scanf("%d%d", &num1, &num2);

    printf("GCD of %d and %d is %d.\n", num1, num2, gcd(num1, num2));

    return 0;
}

int gcd(int n1, int n2)
{
    if(n1 == 0) return n2;
    if(n2 == 0) return n1;

    return( (n1 > n2) ? gcd(n1%n2, n2) : gcd(n1, n2%n1) );
}

Output 1:
Enter 2 positive integer numbers
1980
1617

GCD of 1980 and 1617 is 33.

Know more about ternary operator or conditional operator, watch a separate video tutorial: Ternary Operator / Conditional Operator In C.

For list of all c programming interviews / viva question and answers visit: C Programming Interview / Viva Q&A List

For full C programming language free video tutorial list visit:C Programming: Beginner To Advance To Expert