In this post, we will learn how to find GCD of two numbers using recursion in C Programming language.
The greatest common divisor (GCD) of two nonzero integers a and b is the greatest positive integer d such that d is a divisor of both a and b.
We will define a custom recursive function which will calculate the GCD of two numbers.
So, without further ado, let’s begin this tutorial.
C Program to Find GCD of Two Numbers Using Recursion
// C Program To Find GCD of Two Number Using Recursion
#include <stdio.h>
int GCD(int x, int y);
int main(){
int a, b;
// Asking for Input
printf("Enter Two Positive Integers: \n");
scanf("%d\n %d", &a, &b);
printf("GCD of %d and %d is %d.", a, b, GCD(a, b));
return 0;
}
int GCD(int x, int y){
if( y != 0)
return GCD(y, x % y);
else
return x;
}
Output
Enter Two Positive Integers:
40
412
GCD of 40 and 412 is 4.
How Does This Program Work ?
int a, b;
In this program, we have declared two int data type variables named as a and b.
// Asking for Input
printf("Enter Two Positive Integers: \n");
scanf("%d\n %d", &a, &b);
Then, the user is asked to enter the value of two integers. The value of these two integers will get stored in a and b respectively.
printf("GCD of %d and %d is %d.", a, b, GCD(a, b));
We print the GCD of two numbers using printf() function. Here, we called our custom function which will calculate the GCD of two numbers.
int GCD(int x, int y){
if( y != 0)
return GCD(y, x % y);
else
return x;
}
We have declared a recursive function named GCD which will compute and return the GCD of two numbers.
Conclusion
I hope after going through this post, you understand how to find gcd of two numbers using recursion in C Programming language.
If you have any doubt regarding the program, feel free to contact us in the comment section. We will be delighted to help you
Also Read: