GCD using Recursion

#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;
}

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

This program teaches you how to calculate GCD (Greatest Common Divisor) using Recursion in C++. The Euclidean algorithm is one of the oldest and most efficient algorithms for finding GCD. The recursive implementation is elegant and demonstrates how mathematical algorithms can be expressed naturally through recursion.

---

1. What This Program Does

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.

---

2. Header Files Used

1. #include <iostream>
   • Provides cout and cin for input/output operations.

---

3. 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

---

4. 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

---

5. Base Case

Stopping Condition:

if (b == 0) { return a; }

How it works:

• When b becomes 0, a is the GCD
• Stops recursion
• Returns result
• Essential termination

---

6. Recursive Case

Function Calls Itself:

return gcd(b, a % b);

How it works:

• Swaps parameters: (b, a % b)
• Reduces problem size
• Modulo gives remainder
• Continues until base case

---

7. 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

---

8. 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

---

9. 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

---

10. 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

---

11. 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

---

12. return 0;

This ends the program successfully.

---

Summary

• GCD using Euclidean algorithm: gcd(a, b) = gcd(b, a % b), base case: gcd(a, 0) = a.
• Time complexity: O(log(min(a, b))) - very efficient.
• LCM can be calculated using: lcm(a, b) = (a * b) / gcd(a, b).
• Understanding recursive GCD demonstrates efficient algorithm design.
• Essential for number theory, cryptography, and mathematical computations.

This program is fundamental for learning efficient algorithms, understanding the Euclidean algorithm, and preparing for advanced mathematical programming in C++ programs.