C++ Program to Find GCD Using Recursion

You can find the GCD of two numbers in C++ using recursion with the function int gcd(int a, int b) { return b == 0 ? a : gcd(b, a % b); } which calls itself until the remainder is zero.

Examples

Input48 18

Output6

Input100 25

Output25

Input7 3

Output1

How to Think About It

To find the GCD using recursion, think of the problem as repeatedly replacing the larger number with the remainder of dividing the larger by the smaller until the remainder is zero. When the remainder is zero, the smaller number is the GCD. This uses the property that gcd(a, b) = gcd(b, a % b).

Algorithm

1

Get two input numbers a and b.

2

Check if b is zero; if yes, return a as the GCD.

3

Otherwise, call the function recursively with parameters b and a % b.

4

Repeat until b becomes zero.

Code

cpp

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    if (b == 0)
        return a;
    return gcd(b, a % b);
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    return 0;
}

Output

6

Dry Run

Let's trace gcd(48, 18) through the code

1

Initial call

gcd(48, 18)

2

Check if b is zero

b = 18, not zero, so call gcd(18, 48 % 18)

3

Second call

gcd(18, 12)

4

Check if b is zero

b = 12, not zero, so call gcd(12, 18 % 12)

5

Third call

gcd(12, 6)

6

Check if b is zero

b = 6, not zero, so call gcd(6, 12 % 6)

7

Fourth call

gcd(6, 0)

8

Check if b is zero

b = 0, return a = 6

Call	a	b	a % b	Return Value
1	48	18	12	calls gcd(18,12)
2	18	12	6	calls gcd(12,6)
3	12	6	0	calls gcd(6,0)
4	6	0	-	returns 6

Why This Works

Step 1: Base Case

The recursion stops when b becomes zero, because the GCD of a and 0 is a.

Step 2: Recursive Call

Each recursive call reduces the problem size by replacing a with b and b with a % b, moving closer to the base case.

Step 3: Mathematical Property

This works because the GCD of two numbers also divides their remainder, so gcd(a, b) = gcd(b, a % b).

Alternative Approaches

Iterative approach

cpp

#include <iostream>
using namespace std;

int gcd(int a, int b) {
    while (b != 0) {
        int temp = b;
        b = a % b;
        a = temp;
    }
    return a;
}

int main() {
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    return 0;
}

This uses a loop instead of recursion, which can be more efficient and avoids stack overflow for large inputs.

Using std::gcd from C++17

cpp

#include <iostream>
#include <numeric>
using namespace std;

int main() {
    int a, b;
    cin >> a >> b;
    cout << gcd(a, b) << endl;
    return 0;
}

This uses the built-in <code>std::gcd</code> function from C++17, which is optimized and simple to use.

Complexity: O(log(min(a, b))) time, O(log(min(a, b))) space

Time Complexity

The Euclidean algorithm reduces the problem size roughly by half each step, so it runs in logarithmic time relative to the smaller input.

Space Complexity

Recursive calls add to the call stack, so space is proportional to the recursion depth, which is logarithmic.

Which Approach is Fastest?

The built-in std::gcd is fastest and safest, followed by the iterative approach; recursion is clear but uses more stack space.

Approach	Time	Space	Best For
Recursive	O(log(min(a,b)))	O(log(min(a,b)))	Learning and clarity
Iterative	O(log(min(a,b)))	O(1)	Efficiency and large inputs
std::gcd (C++17)	O(log(min(a,b)))	O(1)	Production code and simplicity