Write a recursive function in C to find GCD (HCF) of two numbers. How to find GCD(Greatest Common Divisor) or HCF(Highest Common Factor) of two numbers using recursion in C program. Logic to find HCF of two numbers using recursion in C programming.

**Example**

**Input**

Input first number: 10 Input second number: 15

**Output**

HCF of 10 and 15 = 5

## Required knowledge

Basic C programming, If else, Functions, Recursion

Must know – Program to find HCF using loop

## Logic to find GCD using recursion

Here in this program we will be using recursive approach of Euclidean algorithm to find GCD of two numbers. The Euclidean algorithm to find GCD is,

Algorithm to find GCD using Euclidean algorithmBegin:functiongcd(a,b)If(b= 0) thenreturnaEnd ifElsereturngcd(b,amodb);End ifEnd functionEnd

## Program to find HCF of two numbers using recursion

```
/**
* C program to find GCD (HCF) of two numbers using recursion
*/
#include <stdio.h>
/* Function declaration */
int gcd(int a, int b);
int main()
{
int num1, num2, hcf;
/* Input two numbers from user */
printf("Enter any two numbers to find GCD: ");
scanf("%d%d", &num1, &num2);
hcf = gcd(num1, num2);
printf("GCD of %d and %d = %d", num1, num2, hcf);
return 0;
}
/**
* Recursive approach of euclidean algorithm to find GCD of two numbers
*/
int gcd(int a, int b)
{
if(b == 0)
return a;
else
return gcd(b, a%b);
}
```

Output

Enter any two numbers to find GCD: 12 30 GCD of 12 and 30 = 6

Happy coding ðŸ˜‰

### Recommended posts

- Function and recursion programming exercise index.
- C program to find LCM of two numbers using recursion.
- C program to generate nth Fibonacci term using recursion.
- C program to find factorial of a number using recursion.
- C program to find power of a number using recursion.
- C program to display array elements using recursion.