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

either or both of x and y are negative. We could keep the precondition and throw an
exception when this occurs, but it is more common in mathematics to return the GCD
of the absolute value of the two values. We can accomplish this by including one
extra case for negatives:
public static int gcd(int x, int y) {
if (x < 0 || y < 0) {
// recursive case with negative value(s)
return gcd(Math.abs(x), Math.abs(y));
} else if (y == 0) {
// base case with y == 0
return x;
} else {
// recursive case with y > 0
return gcd(y, x % y);
}
}
Common Programming Error
Infinite Recursion
Everyone who uses recursion to write programs eventually accidentally writes a
solution that leads to infinite recursion. For example, the following is a slight
variation of the gcd method that doesn't work:
// flawed definition
public static int gcd(int x, int y) {
if (x <= 0 || y <= 0) {
// recursive case with negative value(s)
return gcd(Math.abs(x), Math.abs(y));
} else if (y == 0) {
// base case with y == 0
return x;
} else {
// recursive case with y > 0
return gcd(y, x % y);
}
}
This solution is just slightly different than the one we wrote previously. In the
test for negative values, this code tests whether x and y are less than or equal to 0 .
Continued on next page