java - 当 n 为偶数时优化 x^n 的递归方法

Question

我需要使用 Java 编写一个名为 power 的递归方法，它接受一个双倍 x 和一个整数 n，并返回 x^n。这是我目前所拥有的。

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

}

此代码按预期工作。但是，我正在尝试加倍努力并执行以下可选练习:

“可选挑战:当 n 为偶数时，您可以使用 x^n = (x^(n/2))^2 使此方法更有效。”

我不确定当 n 为偶数时如何实现最后一个公式。我认为我不能为此使用递归。我已经尝试实现以下内容，但它也不起作用，因为我无法将 double 提升到 int 的幂。

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

有人能指出我正确的方向吗？我觉得我错过了一些明显的东西。感谢所有帮助。

Answer 1

这与 x^n == x*(x^(n-1)) 的原理完全相同:为 x^(n/2) 和 (...)^2 插入递归函数，但使确保您没有为 n == 2 输入无限递归(因为 2 也是偶数):

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

或者，您可以只使用中间变量:

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

我也可能只是将 2 作为一种特殊情况处理——并避免使用“and”条件和额外变量:

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

附:我认为这也应该有效:)

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