x^n 的递归方法，针对 n 为偶数时进行了优化

java recursion exponentiation

2022-09-01 05:18:16

我需要使用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为偶数时如何实现最后一个公式。我不认为我可以为此使用递归。我试图实现以下内容，但它也不起作用，因为我不能将双精度转换为int的幂。

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

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

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

答案 2

何时是偶数，公式正是您编写的：除以二，递归调用，然后将结果平方。nnpower

当为奇数时，公式稍微复杂一些：从中减去，进行递归调用，对结果进行平方，然后乘以。n1nn/2x

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

n/2截断结果，因此不显式执行减法。下面是 Java 中的一个实现：1

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

演示。