# Functions Exercises

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.

**Required knowledge**

Basic C programming, If else,for loop,Functions, Recursion

**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 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