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 is , return . 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 . Four calls total. Compare that to checking every number from to . The recursive version is both simpler and faster.
Time complexity: because the remainder shrinks rapidly.
Space complexity: for the call stack.