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

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

HCF (Highest Common Factory)

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

Happy coding 😉

About Pankaj

Pankaj Prakash is the founder, editor and blogger at Codeforwin. He loves to learn new techs and write programming articles especially for beginners. He works at Vasudhaika Software Sols as a Software Design Engineer and manages Codeforwin. In short Pankaj is Web developer, Blogger, Learner, Tech and Music lover.

Follow on: Facebook | Twitter | Google | or

Comments and discussion
Have a doubt, write here. I will help my best.
Before commenting you must escape your source code before commenting. Paste your source code inside
<pre><code> ----Your Source Code---- </code></pre>