Recursion - Building Java Programs: A Back to Basics Approach - page 737

To introduce some variety, let's try to figure out the recursive case first and then
figure out the base case. Suppose, for example, that we are asked to compute the
GCD of 20 and 132. The GCD is 4, because 4 is the largest integer that goes evenly
into both numbers.
There are many ways to compute the GCD of two numbers. One of the most effi-
cient algorithms dates back at least to the time of Euclid and perhaps even farther.
This algorithm eliminates any multiples of the smaller integer from the larger integer.
In the case of 20 and 132, we know that

132 = 20 6 + 12

There are six multiples of 20 in 132, with a remainder of 12. Euclid's algorithm
says that we can ignore the six multiples of 20 and just focus on the value 12. In
other words, we can replace 132 with 12:

gcd(132, 20) = gcd(12, 20)

We haven't figured out the base case yet, but no matter what the base case ends up
being, we're making progress if we can reduce the numbers using Euclid's algorithm.
When you're dealing with nonnegative integers, you can't reduce them forever.
The proof of this principle is beyond the scope of this topic, but that is the basic
idea. This algorithm is easy to express in Java terms because the mod operator gives
us the remainder when one number is divided by another. Expressing this principle in
general terms, we know that

when gcd(x, y) = gcd(x % y, y) y > 0

Again, the proof is beyond the scope of this topic, but given this basic principle we
can produce a recursive solution to the problem. We might try to write the method as
follows:

public static int gcd(int x, int y) {
if (...) {
// base case
...
} else {
// recursive case
return gcd(x % y, y);

}

}

This isn't a bad first attempt, but it has a problem: It's not enough for the solution
to be mathematically correct; we also need our recursive solution to keep reducing
the overall problem to a simpler problem. If we start with the numbers 132 and 20,
the method makes progress on the first call, but then it starts repeating itself:

gcd(132, 20) = gcd(12, 20)
gcd(12, 20) = gcd(12, 20)