kachilous - 4 months ago 5x

Java Question

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.

Answer

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.

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
}
```

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

Source (Stackoverflow)

Comments