Type EUCLID (the GCD recursion theorem made into an algorithm)

Answer

EUCLID(a, b) if b == 0 return a return EUCLID(b, a mod b)

gcd(a,b) = gcd(b, a mod b); the second argument strictly shrinks each call, and gcd(a,0)=a is the base case. O(lg b) calls (Lamé).