C Program To Find GCD of Two Numbers using Recursion: Euclid's Algorithm

Lets write a C program to find GCD(Greatest Common Divisor) or HCF(Highest Common Factor) of two positive integer numbers input by the user using Euclid’s Algorithm and by using Recursive function call logic.

Expected Input/Out
Enter 2 positive integer numbers
1980
1617

GCD of 1980 and 1617 is 33.

Euclid’s Algorithm Logic
If user inputs 2 numbers n1 and n2, reduce the bigger number by modulo dividing it by the smaller number. For example, if n1 is greater than n2, then reduce the value of n1 by replacing it with n1%n2.

Assume that we’ve a function gcd() which returns gcd of 2 numbers passed to it. Ex: gcd(n1, n2);

According to Euclid’s Algorithm, we’ll get the same gcd if we reduce the bigger number by modulo dividing it by smaller number.

If n1 is greater than n2 we need to pass gcd(n1%n2, n2);
If n2 is greater than n1, we need to pass gcd(n1, n2%n1);

We need to recursively execute above 2 lines of logic until either n1 is 0 or until n2 is 0. If n1 is 0, then value present in n2 is the gcd of (n1,n2). If n2 is 0, then value present in n1 is the gcd of (n1,n2).

C Programming Interview / Viva Q&A List

C Programming: Beginner To Advance To Expert

[Sake]

Understood, seriously recursion makes life easier

[chiragbhowmick]

Thank you for doing this in Codeblocks

[tishachoudhuri]

your solution is right, but. You should be assigning the smaller value to a fixed argument. you swapped the positions in else block, should match the syntactic-sugar of if block, Lol ~ Code critic

[randomaysd]

How about java program finding gcf of two numbers using recursion and euclid algorithm?

[arungowda]

Hi sir....beautifully explained....can u pls explain pascal triangle using binomial coefficient