# C program to find GCD (HCF) of two numbers using recursion

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 algorithm
Begin:
function gcd(a, b)
If (b = 0) then
return a
End if
Else
return gcd(b, a mod b);
End if
End function
End```

## 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 😉

Write your doubts or suggestion. I will try my best to help. You must escape source code before commenting. To format your source code paste your source code inside