Recursive method for x^n optimised for when n is even

Question

I need to write a recursive method using Java called power that takes a double x and an integer n and that returns x^n. Here is what I have so far.

public static double power(double x, int n) {
    if (n == 0)
        return 1;
    if (n == 1)
        return x;
    else
        return x * (power(x, n-1));

}

This code works as expected. However, I am trying to go the extra mile and perform the following optional exercise:

"Optional challenge: you can make this method more efficient, when n is even, using x^n = (x^(n/2))^2."

I am not sure how to implement that last formula when n is even. I do not think I can use recursion for that. I have tried to implement the following, but it also does not work because I cannot take a double to the power of an int.

if (n%2 == 0)
        return (x^(n/2))^2;

Can somebody point me in the right direction? I feel like I am missing something obvious. All help appreciated.

Solution 1

It's exactly the same principle as for x^n == x*(x^(n-1)): Insert your recursive function for x^(n/2) and (...)^2, but make sure you don't enter an infinite recursion for n == 2 (as 2 is even, too):

if (n % 2 == 0 && n > 2) 
  return power(power(x, n / 2), 2);
} 

Alternatively, you could just use an intermediate variable:

if (n % 2 == 0) {
  double s = power(x, n / 2);
  return s * s;
}

I'd probably just handle 2 as a special case, too -- and avoid the "and"-condition and extra variable:

public static double power(double x, int n) {
  if (n == 0) return 1;
  if (n == 1) return x;
  if (n == 2) return x * x;
  if (n % 2 == 0) return power(power(x, n / 2), 2);
  return x * (power(x, n - 1));
}

P.S. I think this should work, too :)

public static double power(double x, int n) {
  if (n == 0) return 1;
  if (n == 1) return x;
  if (n == 2) return x * x;
  return power(x, n % 2) * power(power(x, n / 2), 2);
}

Solution 2

When n is even, the formula is exactly what you wrote: divide n by two, call power recursively, and square the result.

When n is odd, the formula is a little more complex: subtract 1 from n, make a recursive call for n/2, square the result, and multiply by x.

if (n%2 == 0)
    return (x^(n/2))^2;
else
    return x*(x^(n/2))^2;

n/2 truncates the result, so subtraction of 1 is not done explicitly. Here is an implementation in Java:

public static double power(double x, int n) {
    if (n == 0) return 1;
    if (n == 1) return x;
    double pHalf = power(x, n/2);
    if (n%2 == 0) {
        return pHalf*pHalf;
    } else {
        return x*pHalf*pHalf;
    }
}

Demo.

Solution 3

Hint: The ^ operation won't perform exponentiation in Java, but the function you wrote, power will.

Also, don't forget squaring a number is the same as just multiplying it by itself. No function call needed.

Solution 4

Making a small change to your function, it will reduce the number of recursive calls made:

public static double power(double x, int n) {
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return x;
    }

    if (n % 2 == 0) {
        double temp = power(x, n / 2);
        return temp * temp;
    } else {
        return x * (power(x, n - 1));
    }
}

Solution 5

Since

x^(2n) = (x^n)^2

you can add this rule to your method, either using the power function you wrote, as Stefan Haustein suggested, or using the regular multiplication operator, since it seems you are allowed to do that.

Note that there is no need for both the base cases n=1 and n=0, one of them suffices (prefferably use the base case n=0, since otherwise your method would not be defined for n=0).

public static double power(double x, int n) {
    if (n == 0)
        return 1;
    else if (n % 2 == 0)
        double val = power(x, n/2);
        return val * val;
    else
        return x * (power(x, n-1));
}

There is no need to check that n>2 in any of the cases.

View more solutions

Comments

[Omar N]

that seems correct, but when I try to implement that code in Java, I get an error "The operator ^ is undefined for the argument type(s) double, int. Perhaps I am missing something?

[Sergey Kalinichenko]

@OmarN This should be straightforward to implement (demo).

[Matthieu M.]

In the spirit of further optimization, one can note that if n%2 == 1 (and thus the last line is reached), then (n-1) % 2 == 0 and thus the latter expression can be further "unrolled": x * power(power(x, (n-1)/2), 2).

[Stefan Haustein]

One could also combine the last two cases into return power(x, n % 2) * power(power(x, n/2), 2); :)

[Matthieu M.]

That too :) Actually, I am curious about power(power(x, n/2), 2) too, since most of the times when I've done it, I've used power(x*x, n/2) (which avoids a function call).

[Mariano]

If you ever edit the question adding those, make sure to place a warning for homework seeking students to stick with the previous.

[Sergey Kalinichenko]

Downvoter: would you mind sharing your reasons for voting down a perfectly correct answer with a fully working demo?