Introduction:
This C program calculates the greatest common divisor (GCD) of two non-negative integers using recursion. The GCD of two integers is the largest positive integer that divides both numbers without leaving a remainder. This program employs the Euclidean algorithm, which simplifies the problem through recursive calls, making it an efficient approach for GCD computation.
#include <stdio.h>
/*
* Program to calculate the greatest common divisor (GCD) of two numbers using recursion.
* This program takes two non-negative integers as input and computes their GCD
* using the Euclidean algorithm, which is efficiently implemented recursively.
*/
// Recursive function to calculate GCD
int gcd(int a, int b) {
// Base case
if (b == 0) {
return a; // GCD found when b reaches 0
}
// Recursive case
return gcd(b, a % b); // Recur with b and the remainder of a divided by b
}
int main() {
int num1, num2;
printf("Enter two non-negative integers: ");
scanf("%d %d", &num1, &num2); // Read two integers
if (num1 < 0 || num2 < 0) {
printf("GCD is not defined for negative numbers.\n");
} else {
int result = gcd(num1, num2);
printf("GCD of %d and %d is: %d\n", num1, num2, result);
}
return 0;
}
Input/Output Block:
Input:
- The user is prompted to enter two non-negative integers.
Example Input:
Enter two non-negative integers: 48 18
Output:
- The program outputs the GCD of the given integers.
Example Output:
GCD of 48 and 18 is: 6
Conclusion:
The GCD calculation program effectively demonstrates the application of recursion in solving mathematical problems. By utilizing the Euclidean algorithm, the program efficiently computes the GCD of two integers, showcasing the power of recursive functions in simplifying complex tasks. This program reinforces fundamental programming concepts, including recursion, input validation, and algorithm design. Overall, it serves as a practical example for understanding how to implement recursive algorithms in C, emphasizing their relevance in computational mathematics.
