GCD using Recursion
Greatest Common Divisor (GCD) using Recursion in C++
IntermediateTopic: Recursion Programs
C++ GCD using Recursion Program
This program helps you to learn the fundamental structure and syntax of C++ programming.
#include <iostream>
using namespace std;
// Recursive function to calculate GCD using Euclidean algorithm
int gcd(int a, int b) {
// Base case
if (b == 0) {
return a;
}
// Recursive case
return gcd(b, a % b);
}
int main() {
int num1, num2;
cout << "Enter two numbers: ";
cin >> num1 >> num2;
// Handle negative numbers
num1 = abs(num1);
num2 = abs(num2);
int result = gcd(num1, num2);
cout << "GCD of " << num1 << " and " << num2 << " = " << result << endl;
// Calculate LCM using GCD
int lcm = (num1 * num2) / result;
cout << "LCM of " << num1 << " and " << num2 << " = " << lcm << endl;
// Test with multiple pairs
cout << "\nGCD of various pairs:" << endl;
int pairs[][2] = {{48, 18}, {100, 25}, {17, 13}, {56, 42}};
for (int i = 0; i < 4; i++) {
int a = pairs[i][0];
int b = pairs[i][1];
cout << "GCD(" << a << ", " << b << ") = " << gcd(a, b) << endl;
}
return 0;
}Output
Enter two numbers: 48 18 GCD of 48 and 18 = 6 LCM of 48 and 18 = 144 GCD of various pairs: GCD(48, 18) = 6 GCD(100, 25) = 25 GCD(17, 13) = 1 GCD(56, 42) = 14
Understanding GCD using Recursion
GCD using Euclidean algorithm: gcd(a, b) = gcd(b, a % b). Base case: gcd(a, 0) = a. Time complexity: O(log(min(a, b))). Efficient algorithm for finding GCD. LCM can be calculated using: lcm(a, b) = (a * b) / gcd(a, b).
Note: To write and run C++ programs, you need to set up the local environment on your computer. Refer to the complete article Setting up C++ Development Environment. If you do not want to set up the local environment on your computer, you can also use online IDE to write and run your C++ programs.