java - 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.

question from:https://stackoverflow.com/questions/32803843/recursive-method-for-xn-optimised-for-when-n-is-even

Answer 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);
}