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

gcd(12, 20) = gcd(12, 20)
gcd(12, 20) = gcd(12, 20)
...
This pattern will lead to infinite recursion. The Euclidean trick helped the first time
around, because for the first call x was greater than y (132 is greater than 20). But the
algorithm makes progress only if the first number is larger than the second number.
Here is the line of code that is causing the problem:
return gcd(x % y, y);
When we compute (x % y) , we are guaranteed to get a result that is smaller than
y . That means that on the recursive call, the first value will always be smaller than the
second value. To make the algorithm work, we need the opposite to be true. We can
achieve this goal simply by reversing the order of the arguments:
return gcd(y, x % y);
On this call we are guaranteed to have a first value that is larger than the second
value. If we trace this version of the method for computing the GCD of 132 and 20,
we get the following sequence of calls:
gcd(132, 20) = gcd(20, 12)
gcd(20, 12) = gcd(12, 8)
gcd(12, 8) = gcd(8, 4)
gcd(8, 4) = gcd(4, 0)
...
At this point we have to decide what the GCD of 4 and 0 is. It may seem strange,
but the answer is 4. In general, gcd(n, 0) is n . Obviously, the GCD can't be any
larger than n , and n goes evenly into n . But n also goes evenly into 0 , because 0 can
be written as an even multiple of n : (0 * n) = 0 .
This observation leads us to the base case. If y is 0 , the GCD is x :
public static int gcd(int x, int y) {
if (y == 0) {
// base case with y == 0
return x;
} else {
// recursive case with y > 0
return gcd(y, x % y);
}
}
This base case also solves the potential problem that the Euclidean formula
depends on y not being 0 . However, we still have to think about the case in which