GCD Using Recursion
Last Updated: June 7, 2026
Understanding the Problem
The greatest common divisor of two numbers is the largest integer that divides both with no remainder. For 48 and 18, the shared divisors are 1, 2, 3, 6, and the greatest is 6. Listing divisors works but is slow, and the Euclidean algorithm finds the answer far more directly.
The Euclidean algorithm rests on one fact: any number that divides both a and b also divides the remainder a % b, and the reverse holds too. So the common divisors of (a, b) are the common divisors of (b, a % b), which means gcd(a, b) = gcd(b, a % b). Replacing the pair with (b, a % b) produces a smaller pair without changing the answer, and repeating that shrinks the numbers quickly.
Key Constraints:
- One of the inputs can be
0. The greatest common divisor ofaand0isa, because every integer divides0andadivides itself. This is the base case. - The inputs are not both
0, so the result is always a positive integer and the problem is well defined. - The remainder
a % bis always smaller thanb, so the second number strictly decreases each step and the recursion reaches0quickly.
Approach 1: Recursive Euclidean
Intuition
The identity gcd(a, b) = gcd(b, a % b) is recursive on its own. To find the divisor of (a, b), find the divisor of the smaller pair (b, a % b), the same kind of problem.
The recursion stops when the second number reaches 0, where gcd(a, 0) is a, since a divides itself and also divides 0. The descent always gets there: a % b is strictly less than b, so the second argument decreases at every step until it hits 0. The first argument then holds the answer and is returned straight back up the chain.
Algorithm
- If
bis0, returna. This is the base case, the greatest common divisor ofaand0. - Otherwise, return the result of calling the function with
banda % b.
Example Walkthrough
Input:
The first call is gcd(48, 18). Since b is not 0, it returns gcd(18, 48 % 18), which is gcd(18, 12). That returns gcd(12, 18 % 12), which is gcd(12, 6). That returns gcd(6, 12 % 6), which is gcd(6, 0). Now b is 0, so the base case returns 6. That value passes back up through every pending call, so gcd(48, 18) is 6. The pair shrank from (48, 18) to (6, 0) in three steps.
Code
- Time Complexity: O(log(min(a, b))). The remainder at least halves every two steps, so the pair shrinks fast.
- Space Complexity: O(log(min(a, b))). One stack frame is held per recursive step until the base case returns.
Approach 2: Iterative Euclidean
Intuition
The recursion only ever carries forward the current pair, so a loop can replace it. Repeatedly set the pair (a, b) to (b, a % b) until b becomes 0, then a holds the answer. This does the same arithmetic as the recursion but reuses a single stack frame instead of nesting calls.
Algorithm
- While
bis not0, compute the remaindera % b, setatob, and setbto that remainder. - When
breaches0, returna.
Example Walkthrough
Input:
The pair starts at (48, 18). The remainder 48 % 18 is 12, so the pair becomes (18, 12). Next 18 % 12 is 6, so the pair becomes (12, 6). Then 12 % 6 is 0, so the pair becomes (6, 0) and the loop stops. The answer is a, which is 6. The loop walked through the same pairs as the recursion, just without adding frames to the call stack.
Code
- Time Complexity: O(log(min(a, b))). The loop runs once per Euclidean step, and the remainder shrinks the pair quickly.
- Space Complexity: O(1). Only the pair and a temporary remainder are stored, with no recursion to grow the stack.