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.

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