C program to find gcd/hcf using Euclidean algorithm using recursion

This C program is to find gcd/hcf using Euclidean algorithm using recursion.HCF(Highest Common Factor)/GCD(Greatest Common Divisor) is the largest positive integer which divides each of the two numbers.For example gcd of 48 and 18 is 6 as divisors of 48 are 1,2,3,4,6,8,12,16,24,48 and divisors of 18 are 1,2,3,6,9,18 , so the greatest common divisor is 6.

Logic

We subtract smaller number from larger number i.e. we decrease the larger number, or gcd will not change if we do it vice versa. So if we keep subtracting repeatedly the larger of two, we end up with gcd.For recursion, instead of performing subtraction, we keep dividing by the smaller number and the algorithm stops when we find remainder 0.

Dry Run of the Program

Take input as n1=12 and n2=8

We enter function gcd()

int gcd(int a,int b)

a=12 and b=8

if(a==0) false

else

return gcd(b%a,a);  i.e. return gcd(8%12,12)  i.e. return gcd(8,12)

A recursive call[gcd(8,12)]

if(a==0) false

else

return gcd(b%a,a);  i.e. return gcd(12%8,8)  i.e. return gcd(4,8)

A recursive call[gcd(4,8)]

if(a==0) false

else

return gcd(b%a,a);  i.e. return gcd(8%4,4)  i.e. return gcd(0,4)

A recursive call[gcd(0,4)]

if(a==0) true

return b;  i.e. return 4….final answer

Program

#include<stdio.h>
 
//Calculates gcd of n1 and n2 recursively
int gcd(int a,int b)
{
    if (a == 0)
        return b;
    else
        return gcd(b%a,a);
}
 
void main()
{
    int n1,n2,answer;
    printf("Enter the two numbers\n");
    scanf("%d%d",&n1,&n2);
    answer=gcd(n1,n2);
    printf("GCD(%d,%d) = %d",n1,n2,answer);
}

Output