GCD - Implementation

Here is the recursive GCD function:

function gcd(a, b)
    if b = 0 then
        return a
    return gcd(b, a mod b)

The entire algorithm is just one line of logic. If $b$ is $0$, return $a$. Otherwise, call gcd(b, a mod b). Trace gcd(48, 18): you get gcd(18, 12), then gcd(12, 6), then gcd(6, 0), which returns $6$. Four calls total. Compare that to checking every number from $1$ to $18$. The recursive version is both simpler and faster.

Time complexity: $O(\log(\min(a, b)))$ because the remainder shrinks rapidly.

Space complexity: $O(\log(\min(a, b)))$ for the call stack.