Skip to main content
CodePeet

CodePeet 444 Complete DSA Sheet

GCD Using Recursion

Try it yourself
EasyProblem

Description

Given two positive integers a and b, return their greatest common divisor, the largest number that divides both, using recursion.

Examples

Example 1

Input: a = 48, b = 18

Output: 6

Explanation: 18 divides neither, but 6 divides both: 48 = 6 × 8 and 18 = 6 × 3, and nothing bigger does.

Example 2

Input: a = 7, b = 13

Output: 1

Explanation: Two different primes share no divisor but 1.

Example 3

Input: a = 20, b = 5

Output: 5

Explanation: 5 divides 20, so it's the answer.

Example 4

Input: a = 5, b = 20

Output: 5

Explanation: The order doesn't matter: the first step swaps them.

Constraints

  • 1 ≤ a, b ≤ 10^9

Editorial

Approach - Euclid's Algorithm

Intuition

Any number that divides both a and b also divides a - b, so gcd(a, b) = gcd(a - b, b). Taking b away again and again until what's left is smaller than b leaves exactly a % b, so in one step: gcd(a, b) = gcd(b, a % b). The pair keeps shrinking, and when the second number reaches 0 the first is the answer, since every number divides 0.

Subtracting one b per call gives the same answer, but for 10^9 and 2 it takes 500 million calls. The remainder does them all at once.

Step-by-Step Explanation

Let's trace Example 1, a = 48, b = 18:

  1. gcd(6, 0) is the base case: it returns 6.
  2. gcd(12, 6) = gcd(6, 12 % 6) = gcd(6, 0).
  3. gcd(18, 12) = gcd(12, 18 % 12) = gcd(12, 6).
  4. gcd(48, 18) = gcd(18, 48 % 18) = gcd(18, 12).
  5. So gcd(48, 18) is 6.

Euclid's Algorithm — Each call hands on the smaller number and the remainder; the answer found at the bottom comes back unchanged.

Algorithm

  1. If b is 0, return a.
  2. Otherwise return gcd(b, a % b).

Code

class Solution {
public:
    int gcd(int a, int b) {
        if (b == 0) return a;
        return gcd(b, a % b);
    }
};

class Solution:
    def gcd(self, a: int, b: int) -> int:
        if b == 0:
            return a
        return self.gcd(b, a % b)

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

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

Complexity Analysis

Time Complexity: O(log min(a, b))

Every two calls at least halve the smaller number, so about 45 calls even for numbers near 10^9.

Space Complexity: O(log min(a, b))

One frame per call waits on the stack.

Common Mistakes

Each of these looks right on a quick read, and the tests still reject it. The outputs below come from running the code.

Subtracting instead of taking the remainder. return self.gcd(a - b, b)

On a = 1000000000, b = 2 it fails with RecursionError: maximum recursion depth exceeded in comparison instead of returning 2. gcd(a, b) = gcd(a - b, b) is true, but each call takes away the smaller number only once. For 10^9 and 2 that's 500 million calls, far past Python's recursion limit. The remainder, a % b, does all those subtractions in one step.

Stopping at b = 1. if b == 1:

On a = 4, b = 2 it fails with ZeroDivisionError: integer division or modulo by zero instead of returning 2. The pair shrinks until the second number is 0, and that's the only base case. Stopping at 1 lets a pair like (2, 0) through to 2 % 0, a division by zero.

Returning b at the base case. return b

On a = 48, b = 18 it returns 0; the answer is 6. When b reaches 0, the answer is a: gcd(a, 0) = a, since every number divides 0. b is 0 there.

Where This Pattern Is Taught

This problem practises a smaller call that shrinks two numbers at once. It's taught in Introduction to Recursion.