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

pow(3, 5) = 3 * pow(3, 4)

pow(3, 4) = 3 * pow(3, 3)

pow(3, 3) = 3 * pow(3, 2)

pow(3, 2) = 3 * pow(3, 1)

pow(3, 1) = 3 * pow(3, 0)

pow(3, 0) = 1

pow(3, 1) = 3 * 1 = 3

pow(3, 2) = 3 * 3 = 9

pow(3, 3) = 3 * 9 = 27

pow(3, 4) = 3 * 27 = 81

pow(3, 5) = 3 * 81 = 243

Notice that we make a series of six recursive calls in a row until we reach the base
case of computing 3 to the 0 power. That call returns the value 1 and then the recur-
sion unwinds, computing the various answers as it returns from each method call.
It is useful to think about what will happen if someone violates the precondition by
asking for a negative exponent. For example, what if someone asked for pow(3, -1) ?
The method would recursively ask for pow(3, -2) , which would ask for pow(3, -3) ,
which would ask for pow(3, -4) , and so on. In other words, it would lead to an infinite
recursion. In a sense, it's okay for this to occur, because the person calling the method
should pay attention to the precondition and should not enter a negative exponent. But
it's not much work for us to handle this case in a more elegant manner. Our solution is
structured as a series of cases, so we can simply add a new case for illegal exponents:

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 {
// recursive case with y > 0
return x * pow(x, y - 1);

}

}

One of the advantages of writing functions recursively is that if we can identify
other cases, we can potentially make the function more efficient. For example,
suppose that you want to compute 2 16 . In its current form, the method will multiply
2 by 2 by 2 a total of 16 times. But we can do better than that. If y is an even
exponent, then

(x 2 ) 2 x y =

So instead of computing 2 16 , we can compute 4 8 , which is simpler. Adding this
case to our method is relatively easy: