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. Calculating GCD of two numbers using recursive function.

Input first number: 10

Input second number: 15

Output GCD: 5

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:

Happy coding ;)

**Example:**Input first number: 10

Input second number: 15

Output GCD: 5

### Required knowledge

Basic C programming, Function, Recursion### Logic to find GCD using recursion

We have already seen in one of our previous post about what is GCD (Greatest Common Divisor) and how to find GCD using loop.Algorithm to find GCD using Euclidean algorithmBegin:functiongcd(a,b)If(b= 0) thenreturnaEnd ifElsereturngcd(b,amodb);End ifEnd functionEnd

### Program to find GCD 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; /* Reads 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\n", 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

30

GCD of 12 and 30 = 6

Happy coding ;)

### You may also like

- Function and recursion programming exercises index.
- C program to find LCM of two numbers using recursion.
- C program to display elements of array using recursion.
- C program to find sum of all elements of an array using recursion.
- C program to find factorial of any number using recursion.
- C program to find fibonacci series up to n terms.
- C program to find reverse of any number using recursion.
- C program to check palindrome numbers using recursion.
- C program to find sum of all even or odd numbers using recursion.
- C program to check prime, armstrong and perfect numbers using functions .

< code >< pre > -- Your source code -- < /pre >< /code > (Remove spaces from pre and code tags).