kachilous - 1 year ago 76
Java Question

# Recursively compute the value of base to the n power

Here is what I have for my solution:

`````` public int powerN(int base, int n) {

if(n == 0)
return 1;

else if(n % 2 == 0)
return base * base;

else
return base * powerN(base, n-1);

}
``````

However, if n > 3 then this function doesn't work.
For instance, powerN(2, 4) yields 4 and powerN(2, 5) yields 8.
I know that a much simpler solution exists, but it just bothers me that I can't figure out why this is not working correctly.

## Into pseudocode

Let me translate your code into pseudocode:

``````public int powerN(int base, int exponent)  {
if the exponent is 0
then return 1
otherwise, if the exponent is even
then return base * base
otherwise
base * powerN(base, exponent - 1)
}
``````

The second branch has a logic error. What your code is saying is this: "As long as the exponent is even, the result should be `base * base` (that is, `base` squared)". You've already mentioned that this is the result you get when you run your code.

## How to solve it

What you probably want to do is to raise `base` to half the `exponent` (`base * base * base * ...` for `exponent / 2` times), and then multiply that number by itself. That way, you get `base` multiplied by itself `exponent` times.

In pseudocode:

``````otherwise, if the exponent is even
then return powerN(base, exponent / 2) * powerN(base, exponent / 2)
``````

Realistically, this would actually be the following:

``````otherwise, if the exponent is even
then {
let x = powerN(base, exponent / 2)
return x * x
}
``````

## Done. Mostly.

Translate that back to Java and you'll be set.

Recommended from our users: Dynamic Network Monitoring from WhatsUp Gold from IPSwitch. Free Download