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

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.
GCD of two numbers
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 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

Happy coding ;)


Any doubt or suggestion write here. I will try my best to help. Before posting your code you must escape it to view. To format your source code and use format highlighting, post your source code inside
< code >< pre > -- Your source code -- < /pre >< /code > (Remove spaces from pre and code tags).

No comments:

Post a Comment