Java Reference
In-Depth Information
The method we want to write will look like the following:
// pre : y >= 0
// post: returns x
∧
y
public static int pow(int x, int y) {
...
}
We could obviously solve this problem by writing a loop, but we want to explore
how to write the method recursively. Again, we should start by thinking about differ-
ent cases. What would be the easiest exponent to compute? It's pretty easy to com-
pute x
1
, so that's a good candidate, but there is an even more basic case. The simplest
possible exponent is 0. By definition, any integer to the 0 power is considered to be 1.
So we can begin our solution with the following code:
public static int pow(int x, int y) {
if (y == 0) {
// base case with y == 0
return 1;
} else {
// recursive case with y > 0
...
}
}
In the recursive case we know that
y
is greater than
0
. In other words, there will be
at least one factor of
x
in the result. We know from mathematics that
x
y
= x
x
y
-1
This equation expresses
x
to the
y
power in terms of
x
to a smaller power,
(y - 1)
.
Therefore, it can serve as our recursive case. All we have to do is to translate it into its
Java equivalent:
public static int pow(int x, int y) {
if (y == 0) {
// base case with y == 0
return 1;
} else {
// recursive case with y > 0
return x * pow(x, y - 1);
}
}
This is a complete recursive solution. Tracing the execution of a recursive function
is a little more difficult than using a
void
method, because we have to keep track of
the values that are returned by each recursive call. The following is a trace of execu-
tion showing how we would compute 3
5
:
Search WWH ::
Custom Search