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

Required knowledge

Logic to find GCD using recursion

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); 
}