Greatest common divisor (Euclidean algorithm)
Easy TimeO(log min(a, b)) SpaceO(log min(a, b))
The greatest common divisor of two numbers is the largest number that divides both of them exactly — for 48 and 18 it is 6. Given two positive integers a and b, return theirs. The greatest common divisor of a number and 0 is that number itself.
Examples
Example 1
- Input
- a = 48b = 18
- Output
648 = 6 × 8and18 = 6 × 3, and nothing larger divides both.
Example 2
- Input
- a = 17b = 5
- Output
- 17 and 5 share no divisor above 1, so the answer is
11.
The Code
function gcd(a, b) {
if (b === 0) return a;
return gcd(b, a % b);
}
gcd(48, 18);Done
More like this
All recursion examples (13) →- Fibonacci The classic branching recursion — every call spawns two more.
- Factorial The simplest linear recursion — one call, one multiply.
- Tower of Hanoi Move a stack of disks by trusting the recursion for the rest.
- Power Raise a number to a power one multiply at a time.
- Sum of digits Peel one digit off at a time with the modulo trick.
- Mutual recursion Two functions that call each other all the way down.