Home » C programs » C recursion programs

C program to find the GCD (Greatest Common Divisor) of given numbers using recursion

Here, we are going to learn how to find the GCD (Greatest Common Divisor) of given numbers using recursion in C language?
Submitted by Nidhi, on August 03, 2021

Problem statement

Read two integer numbers, and find the GCD (Greatest Common Divisor) of given numbers.

C program to find the GCD (Greatest Common Divisor) of given numbers using recursion

The source code to find the GCD (Greatest Common Divisor) of a given number using recursion is given below. The given program is compiled and executed using GCC compile on UBUNTU 18.04 OS successfully.

// C program to find the GCD
// (Greatest Common Divisor) of given numbers
// using recursion

#include <stdio.h>

int calGCD(int num1, int num2)
{
    while (num1 != num2) {
        if (num1 > num2)
            return calGCD(num1 - num2, num2);
        else
            return calGCD(num1, num2 - num1);
    }
    return num1;
}

int main()
{
    int num1 = 0;
    int num2 = 0;

    printf("Enter Number1: ");
    scanf("%d", &num1);

    printf("Enter Number2: ");
    scanf("%d", &num2);

    printf("The Greatest Common Divisor is: %d\n", calGCD(num1, num2));

    return 0;
}

Output

RUN 1:
Enter Number1: 10
Enter Number2: 20
The Greatest Common Divisor is: 10

RUN 2:
Enter Number1: 10
Enter Number2: 225
The Greatest Common Divisor is: 5

RUN 3:
Enter Number1: 117
Enter Number2: 10
The Greatest Common Divisor is: 1

Explanation

In the above program, we created two functions calGCD() and main(). The calGCD() function is a recursive function, which is used to find the Greatest Common Divisor of specified numbers.

In the main() function, we read two integer numbers num1 and num2 from the user and called calGCD() function, and printed the GCD of given numbers on the console screen.

C Recursion Programs »