Euclid's recursive step keeps the GCD unchanged

Replacing (48, 18) with (18, 48 % 18) preserves the GCD

For the running example, 48 % 18 is 12, because 48 = 2 * 18 + 12. The recursive step changes gcd(48, 18) into gcd(18, 12). This does not discard the factors that matter. It replaces the larger number with the remainder left after removing whole copies of the second number.

A common divisor of 48 and 18 also divides 48 - 2 * 18, which is 12. So every common divisor of 48 and 18 is a common divisor of 18 and 12. The reverse direction works too: a number that divides 18 and 12 divides 2 * 18 + 12, which is 48. Therefore the two pairs have exactly the same common divisors, including their greatest common divisor.

When the second number reaches 0, the first number is the answer

The recursive process stops at gcd(6, 0). The answer is 6 because every positive divisor of 6 also divides 0: multiplying any integer by 0 gives 0. The common divisors of 6 and 0 are therefore exactly the divisors of 6, and the greatest one is 6.

For positive integer inputs such as 48 and 18, the base case checks whether the second number is 0. That check must happen before computing another remainder. Once the second number is 0, there is no valid nonzero divisor to use as the divisor in a new modulo operation, and the first number already contains the answer.

gcd(6, 0) -> 6

The calls shrink from (48, 18) to (6, 0) and return the same answer

Starting with gcd(48, 18), calculate 48 % 18 = 12 and make the next call gcd(18, 12). That call calculates 18 % 12 = 6 and makes gcd(12, 6). Next, 12 % 6 = 0, so the next call is gcd(6, 0). The second number has now reached the base case.

gcd(48, 18)
  48 % 18 = 12
  gcd(18, 12)
    18 % 12 = 6
    gcd(12, 6)
      12 % 6 = 0
      gcd(6, 0) returns 6
    returns 6
  returns 6
returns 6

The call gcd(6, 0) returns 6 immediately. The waiting call gcd(12, 6) does not combine that result with another value, it returns the same 6. The same happens in gcd(18, 12) and gcd(48, 18). The recursive calls build the chain downward, and the single base-case value travels unchanged upward.

12 % 6 = 0
gcd(12, 6) calls gcd(6, __)

The shrinking remainder gives logarithmic time and stack space

Let T(a, b) describe the time for positive inputs while the second number is not zero. One recursive step computes a remainder and makes the next call, so the applied recurrence is T(a, b) = T(b, a % b) + O(1). The base case is T(a, 0) = O(1), because it checks the second number and returns the first.

For the running example, the recurrence follows four calls: T(48, 18) becomes T(18, 12), then T(12, 6), then T(6, 0), which takes constant time. Each remainder is smaller than the divisor that produced it, so the pair shrinks quickly instead of trying every possible divisor.

For positive inputs a and b, the running time is O(log(min(a, b))). Each call performs only constant extra work: one zero check, one modulo operation when needed, and one recursive call. The recursive stack also holds one frame per call, so its space usage is O(log(min(a, b))). The stored frames are released as the returned value 6 moves back upward.