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

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