The greatest common divisor (G.C.D) of two numbers is the largest positive integer that divides both numbers without leaving a remainder. This article will discuss a C Program to Find G.C.D Using Recursion. We will explore various approaches to solve this problem with examples, explanations, and outputs.
Prerequisites
Before diving into the examples, you should be familiar with:
- Basic C syntax and structure.
- Functions and recursion in C.
- Understanding of the Euclidean algorithm for finding G.C.D.
Understanding the Problem
The task is to find the G.C.D of two numbers using a recursive function. The G.C.D of two numbers is the largest number that can divide both numbers without leaving a remainder. The Euclidean algorithm is a popular method for computing the G.C.D.
Example 1: Basic Recursion Using Euclidean Algorithm
1.1 Explanation
In this example, we will use the Euclidean algorithm to find the G.C.D. The algorithm is based on the principle that the G.C.D of two numbers a and b (where a > b) is the same as the G.C.D of b and a % b. This process is repeated until b becomes 0, at which point a is the G.C.D.
1.2 Program: Basic Recursion
#include <stdio.h>
int gcd(int a, int b);
int main() {
int num1, num2;
printf("Enter two integers: ");
scanf("%d %d", &num1, &num2);
printf("G.C.D of %d and %d is: %d\n", num1, num2, gcd(num1, num2));
return 0;
}
int gcd(int a, int b) {
if (b == 0)
return a;
else
return gcd(b, a % b);
}
1.3 Output
Enter two integers: 56 98
G.C.D of 56 and 98 is: 14
Example 2: Recursion with Validation
2.1 Explanation
This example includes input validation to ensure that the numbers are positive integers. It uses the same Euclidean algorithm but adds a check to handle negative inputs gracefully.
2.2 Program: Recursion with Validation
#include <stdio.h>
int gcd(int a, int b);
int main() {
int num1, num2;
printf("Enter two positive integers: ");
scanf("%d %d", &num1, &num2);
if (num1 <= 0 || num2 <= 0) {
printf("Please enter positive integers only.\n");
} else {
printf("G.C.D of %d and %d is: %d\n", num1, num2, gcd(num1, num2));
}
return 0;
}
int gcd(int a, int b) {
if (b == 0)
return a;
else
return gcd(b, a % b);
}
2.3 Output
Enter two positive integers: -56 98
Please enter positive integers only.
Enter two positive integers: 56 98
G.C.D of 56 and 98 is: 14
Example 3: Extended Euclidean Algorithm
3.1 Explanation
The extended Euclidean algorithm not only finds the G.C.D but also the coefficients of Bézout’s identity, which are the integers x and y such that ax + by = gcd(a, b). This example demonstrates how to implement this using recursion.
3.2 Program: Extended Euclidean Algorithm
#include <stdio.h>
int gcdExtended(int a, int b, int *x, int *y);
int main() {
int num1, num2, x, y;
printf("Enter two integers: ");
scanf("%d %d", &num1, &num2);
int gcd = gcdExtended(num1, num2, &x, &y);
printf("G.C.D of %d and %d is: %d\n", num1, num2, gcd);
printf("Coefficients x and y are: %d and %d\n", x, y);
return 0;
}
int gcdExtended(int a, int b, int *x, int *y) {
if (a == 0) {
*x = 0;
*y = 1;
return b;
}
int x1, y1;
int gcd = gcdExtended(b % a, a, &x1, &y1);
*x = y1 - (b / a) * x1;
*y = x1;
return gcd;
}
3.3 Output
Enter two integers: 56 98
G.C.D of 56 and 98 is: 14
Coefficients x and y are: -1 and 1
Conclusion
In this article, we explored various C Program to Find G.C.D Using Recursion. The examples covered different techniques:
- Basic Recursion: Simple Euclidean algorithm.
- Recursion with Validation: Adding input validation for robustness.
- Extended Euclidean Algorithm: Finding Bézout coefficients along with G.C.D.
Each example provided a different perspective on solving the problem, demonstrating the flexibility and power of recursion. By understanding these examples, you can tackle similar problems and optimize your solutions for better performance.