GCD using Recursion
Greatest Common Divisor (GCD) using Recursion in C++
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;
}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
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:
GCD is fundamental for many mathematical and programming problems.
---
2. Header Files Used
---
3. Understanding GCD
GCD Definition
:
Example
:
---
4. Euclidean Algorithm
Mathematical Principle
:
How it works
:
---
5. Base Case
Stopping Condition
:
if (b == 0) {
}
return a;How it works
:
---
6. Recursive Case
Function Calls Itself
:
return gcd(b, a % b);How it works
:
---
7. Recursion Flow
Example: gcd(48, 18)
:
---
8. Calculating LCM
Using GCD
:
lcm(a, b) = (a * b) / gcd(a, b)
How it works
:
---
9. Time Complexity
Efficiency
:
Why Efficient
:
---
10. When to Use Recursive GCD
Best For
:
Example Scenarios
:
---
11. Important Considerations
Efficiency
:
Mathematical Foundation
:
Recursive Elegance
:
---
12. return 0;
This ends the program successfully.
---
Summary
This program is fundamental for learning efficient algorithms, understanding the Euclidean algorithm, and preparing for advanced mathematical programming in C++ programs.
Let us now understand every line and the components of the above program.
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.
Practical Learning Notes for GCD using Recursion
This C++ program is part of the "Recursion Programs" topic and is designed to help you build real problem-solving confidence, not just memorize syntax. Start by understanding the goal of the program in plain language, then trace the logic line by line with a custom input of your own. Once you can predict the output before running the code, your understanding becomes much stronger.
A reliable practice pattern is to run the original version first, then modify only one condition or variable at a time. Observe how that single change affects control flow and output. This deliberate style helps you understand loops, conditions, and data movement much faster than copying full solutions repeatedly.
For interview preparation, explain this solution in three layers: the high-level approach, the step-by-step execution, and the time-space tradeoff. If you can teach these three layers clearly, you are ready to solve close variations of this problem under time pressure.