C Program to Find GCD of Two Numbers Using Recursion

Here we will write a C program to find the gcd of two numbers using recursion. This is another example of the recursive function. A recursive function is used to solve the problem.

Prerequisites:- Recursion in C Programming Language

Program description:- Write a C program to find the greatest common divisor (GCD) of given two non-negative integers using recursion.

The Highest common factor (HCF) of two or more numbers is the greatest number which divides each of them exactly. Greatest Common Measure(GCM) and Greatest Common Divisor(GCD) are the other terms used to refer to HCF. Example: HCF of 60 and 75 = 15 because 15 is the highest number which divides both 60 and 75 exactly.

We have already find GCD or HCF using for loop and while loop. Now, the same problem will be find using Recursion.

C program to find gcd of two numbers using recursion

#include<stdio.h>

// recursive function to find gcd of two number
int gcd(int a, int b)
{
     if(b!=0)
         return gcd(b, a%b); // general case
     else
         return a; // base case
}

int main()
{
     int n1, n2, result;

     printf("Enter two numbers: ");
     scanf("%d %d",&n1,&n2);

     result = hcf(n1,n2);
     printf("GCD of %d and %d = %d",n1,n2,result);

     return 0;
}

Output for the different test-cases:-

Enter two numbers: 48 18
GCD of 48 and 18 = 6

Enter two numbers: 50 75
GCD of 50 and 75 = 25

In this program, one recursive function gcd is defined which takes two integer arguments and returns int data type. From the main function, the recursive function is called with user-entered value. The parameters of the gcd function hold the value of arguments. Later in the recursive function gcd, through general case gcd(b, a%b) again the function is called until b!=0; Finally, the result is passed back to the main function, and printf() function displayed the result to the screen.

If you enjoyed this post, share it with your friends. Do you want to share more information about the topic discussed above or do you find anything incorrect? Let us know in the comments. Thank you!