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

**Example**

**Input**

Input first number: 10 Input second number: 15

**Output**

HCF of 10 and 15 = 5

## Required knowledge

Basic C programming, Function, 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/HCF of two given numbers. The Euclidean algorithm to find GCD goes below:

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.

<pre><code> ----Your Source Code---- </code></pre>