GCD using Recursion in C++
Greatest Common Divisor (GCD) using Recursion in C++.
IntermediateRecursion ProgramsExample 4 of 5
gcd-using-recursion.cpp
1#include <iostream>2using namespace std;34// Recursive function to calculate GCD using Euclidean algorithm5int gcd(int a, int b) {6 // Base case7 if (b == 0) {8 return a;9 }1011 // Recursive case12 return gcd(b, a % b);13}1415int main() {16 int num1, num2;1718 cout << "Enter two numbers: ";19 cin >> num1 >> num2;2021 // Handle negative numbers22 num1 = abs(num1);23 num2 = abs(num2);2425 int result = gcd(num1, num2);2627 cout << "GCD of " << num1 << " and " << num2 << " = " << result << endl;2829 // Calculate LCM using GCD30 int lcm = (num1 * num2) / result;31 cout << "LCM of " << num1 << " and " << num2 << " = " << lcm << endl;3233 // Test with multiple pairs34 cout << "\nGCD of various pairs:" << endl;35 int pairs[][2] = {{48, 18}, {100, 25}, {17, 13}, {56, 42}};3637 for (int i = 0; i < 4; i++) {38 int a = pairs[i][0];39 int b = pairs[i][1];40 cout << "GCD(" << a << ", " << b << ") = " << gcd(a, b) << endl;41 }4243 return 0;44}
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
What's going on
The program demonstrates recursive GCD calculation:
Euclidean algorithm using recursion
Finding greatest common divisor
Calculating LCM using GCD
Efficient recursive implementation
GCD is fundamental for many mathematical and programming problems.
Header Files Used
1.#include <iostream>
Provides cout and cin for input/output operations.
Understanding GCD
GCD Definition
:
Largest positive integer that divides both numbers
No remainder when dividing both
Common factor of both numbers
Fundamental in number theory
Example
:
GCD(48, 18) = 6
48 ÷ 6 = 8, 18 ÷ 6 = 3
6 is largest common divisor
Euclidean Algorithm
Mathematical Principle
:
gcd(a, b) = gcd(b, a % b)
Repeatedly apply until b = 0
When b = 0, gcd = a
Efficient and elegant
How it works
:
Reduces problem size each step
Uses modulo operation
Converges quickly
Logarithmic time complexity
Base Case
Stopping Condition
:
if (b == 0) {
}
1return a;
How it works
:
When b becomes 0, a is the GCD
Stops recursion
Returns result
Essential termination
Recursive Case
Function Calls Itself
:
1return gcd(b, a % b);
How it works
:
Swaps parameters: (b, a % b)
Reduces problem size
Modulo gives remainder
Continues until base case
Recursion Flow
Example: gcd(48, 18)
:
1.gcd(48, 18) → gcd(18, 48 % 18) = gcd(18, 12)
2.gcd(18, 12) → gcd(12, 18 % 12) = gcd(12, 6)
3.gcd(12, 6) → gcd(6, 12 % 6) = gcd(6, 0)
4.Base case: b = 0, return 6
5.Result: GCD = 6
Calculating LCM
Using GCD
:
lcm(a, b) = (a * b) / gcd(a, b)
How it works
:
Relationship between GCD and LCM
Product divided by GCD
Efficient calculation
Uses computed GCD
Time Complexity
Efficiency
:
O(log(min(a, b)))
Very efficient algorithm
Logarithmic time
Fast even for large numbers
Why Efficient
:
Problem size reduces quickly
Modulo operation efficient
Few recursive calls
Optimal algorithm
When to Use Recursive GCD
Best For
:
Finding common divisors
Simplifying fractions
Calculating LCM
Number theory problems
Cryptography applications
Example Scenarios
:
Fraction simplification
Modular arithmetic
Cryptography
Algorithm design
Mathematical computations
Important Considerations
Efficiency
:
Very efficient algorithm
Logarithmic time complexity
Optimal for GCD calculation
Industry standard
Mathematical Foundation
:
Based on Euclidean algorithm
Proven mathematical principle
Efficient and correct
Widely used
Recursive Elegance
:
Natural recursive structure
Simple implementation
Easy to understand
Demonstrates recursion power
return 0;
This ends the program successfully.