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

Question

我需要使用称为 power 的 Java 编写一个递归方法，该方法采用双精度 x 和整数 n 以及 returns 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));

}

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

"Optional challenge: you can make this method more efficient, when n is even, using 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));
}

P.S。我认为这也应该有效:)

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

Answer 2

当n为偶数时，公式就是你写的：将n除以二，递归调用power，求平方

当n为奇数时，公式稍微复杂一点：[=12=减去1，递归调用n/2，对结果进行平方，并乘以 x.

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

n/2 截断结果，因此 1 的减法未明确完成。这是 Java 中的一个实现：

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

Demo.

Answer 3

提示：^ 运算不会在 Java 中执行求幂运算，但您编写的函数 power 会。

此外，请不要忘记对一个数求平方与将它自相乘是一样的。无需函数调用。

Answer 4

对你的函数做一个小改动，它会减少递归调用的次数：

public static double power(double x, int n) {
    if (n == 0) {
        return 1;
    }
    if (n == 1) {
        return x;
    }

    if (n % 2 == 0) {
        double temp = power(x, n / 2);
        return temp * temp;
    } else {
        return x * (power(x, n - 1));
    }
}

Answer 5

自

x^(2n) = (x^n)^2

您可以将此规则添加到您的方法中，或者使用您编写的幂函数，如 Stefan Haustein 所建议的，或者使用常规乘法运算符，因为您似乎被允许这样做。

请注意，基本情况 n=1 和 n=0 都不需要，其中一个就足够了（最好使用基本情况 n=0，否则你的方法将不会为 n=0 定义).

public static double power(double x, int n) {
    if (n == 0)
        return 1;
    else if (n % 2 == 0)
        double val = power(x, n/2);
        return val * val;
    else
        return x * (power(x, n-1));
}

在任何情况下都不需要检查 n>2。

Answer 6

这只是提醒我可以做更多的优化以及以下代码。

class Solution:
# @param x, a float
# @param n, a integer
# @return a float
def pow(self, x, n):
    if n<0:
        return 1.0/self.pow(x,-n)
    elif n==0:
        return 1.0
    elif n==1:
        return x
    else:
        m = n & (-n)
        if( m==n ):
            r1 = self.pow(x,n>>1)
            return r1*r1
        else:
            return self.pow(x,m)*self.pow(x,n-m)

更多的是可以记住中间结果，避免冗余计算。

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

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

java

recursion

exponentiation