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

public static int pow(int x, int y) {
if (y < 0) {
throw new IllegalArgumentException("negative exponent: " + y);
} else if (y == 0) {
// base case with y == 0
return 1;
} else if (y % 2 == 0) {
// recursive case with y > 0, y even
return pow(x * x, y / 2);
} else {
// recursive case with y > 0, y odd
return x * pow(x, y - 1);
}
}
This version of the method is more efficient than the original. The following is a
trace of execution for computing 2 16 :
pow(2, 16) = pow(4, 8)
pow(4, 8) = pow(16, 4)
pow(16, 4) = pow(256, 2)
pow(256, 2) = pow(65536, 1)
pow(65536, 1) = 65536 * pow(65536, 0)
pow(65536, 0) = 1
pow(65536, 1) = 65536 * 1 = 65536
pow(256, 2) = 65536
pow(16, 4) = 65536
pow(4, 8) = 65536
pow(2, 16) = 65536
Without the special case for even exponents, this call would have required 17 dif-
ferent calls on pow (16 recursive cases and one base case).
Greatest Common Divisor
In mathematics, we often want to know the largest integer that goes evenly into two
different integers, which is known as the greatest common divisor (or GCD) of the
two integers. Let's explore how to write a GCD method recursively.
For now, let's not worry about negative values of x and y . We want to write the
following method:
// pre: x >= 0, y >= 0
// post: returns the greatest common divisor of x and y
public static int gcd(int x, int y) {
...
}