Given two non-negative integers, recursively compute and return their greatest common divisor.

In mathematics, the greatest common divisor (GCD) of two positive integers is the largest number that divides both of them without leaving a remainder. For example:

The GCD of 15 and 25 is 5

The GCD of 21 and 28 is 7

The GCD of 13 and 17 is 1 (when two numbers have no common divisors other than 1, they're called relatively prime)

Precondition: a > b for all inputs.

One of the oldest known algorithms for computing the GCD comes from the Greek mathematician Euclid, who discovered a clever way to compute the GCD without having to factor both numbers.

EUCLID'S ALGORITHM

The GCD of any number and 0 is the non-zero number.

Otherwise, the GCD of any two numbers is the GCD of the smaller of the two numbers (b, because of the precondition) and the remainder of the two numbers.

This is a classic divide-and-conquer approach — break a hard problem into a simpler one of the same type.

WORKED EXAMPLE

Let’s say you want to find the greatest common divisor (GCD) of 1071 and 462. That means you're looking for the largest number that divides both 1071 and 462 evenly. The GCD of 1071 and 462 is the GCD of the second input 462 and the remainder operation between the two inputs. 1071 % 462 evaluates to 147, so the next step is to find the GCD of 462 and 147.

That requires finding the next remainder. 462 % 147 evaluates to 21, so we now need to find GCD of 147 and 21. 147 % 21 evaluates to 0, so we call GCD of 21 and 0.

GCD of 21 and 0 is a base case because the b input has the value 0.

What we do in the base case is return the nonzero input (21) to the prior call. We now know that GCD of 21 and 0 is 21. So that means GCD of 147 and 21 is 21, which returns all the way back up to the original question. GCD of 462 and 147 is 21, and GCD of 1071 and 462 is also 21.