2. For two integers m and n, their GCD (Greatest Common Divisor) can be computed
ID: 3857846 • Letter: 2
Question
2. For two integers m and n, their GCD (Greatest Common Divisor) can be computed by a recursive function. Write a recursive function gcd(m,n) to find their Greatest Common Divisor. Once m is 0, the function returns n. Once n is 0, the function returns m. If neither is 0, the function can recursively calculate the Greatest Common Divisor with two smaller parameters. One is n, the second is m mod n. Your program should follow the instructions of this question, otherwise you will not get the credit
Explanation / Answer
Code :
//we need another condition so i added another if .please find the code and feel free to ask if u have any doubts
#include <stdio.h>
//The gcd function starts
int gcd(int m, int n)
{
if (m == 0) {
return n; // if m=0 it returns n
}else if(n == 0){
return m; // if n=0 it returns m
}else if (m >= n ) {
return gcd(n, (m % n)); // if m>=n calling gcd function recursevely
}else if(n >= m){
return gcd(m, (n % m)); // if n>=m calling gcd function recursevely
}
}
int main(void)
{
int m, n, gc;
// Enter two integers prompt and initilizing values to m and n
printf(" Enter two numbers to find gcd : ");
scanf("%d%d", &m, &n);
//calling gcd function
gc = gcd(m,n);
// printing gcd value of m and n
printf(" The GCD of %d and %d is %d ", m, n, gc);
return 0;
}
Outpit :
akolli@smarupureddy:~/Videos/practice/practice$ gcc gcd.c
akolli@smarupureddy:~/Videos/practice/practice$ ./a.out
Enter two numbers to find gcd : 100 70
The GCD of 100 and 70 is 10
akolli@smarupureddy:~/Videos/practice/practice$ gcc gcd.c
akolli@smarupureddy:~/Videos/practice/practice$ ./a.out
Enter two numbers to find gcd : 70 100
The GCD of 70 and 100 is 10
akolli@smarupureddy:~/Videos/practice/practice$ gcc gcd.c
akolli@smarupureddy:~/Videos/practice/practice$ ./a.out
Enter two numbers to find gcd : 0 40
The GCD of 0 and 40 is 40
akolli@smarupureddy:~/Videos/practice/practice$ gcc gcd.c
akolli@smarupureddy:~/Videos/practice/practice$ ./a.out
Enter two numbers to find gcd : 40 0
The GCD of 40 and 0 is 40
Related Questions
drjack9650@gmail.com
Navigate
Integrity-first tutoring: explanations and feedback only — we do not complete graded work. Learn more.