# 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