Java递归求幂方法使递归更有效

MAM安娜：

我想更改此指数方法（n是指数）：

public static double exponentiate(double x, int n) {
    counter++; 
    if (n == 0) {
        return 1.0;
    } else if (n == 1) {
        return x;
    } else {
        return x * exponentiate(x, n - 1);
    }
}

我想更改该方法以使其更有效，因此不用使用MATH类，该方法就不会打开n次，而是最多（n / 2 + 1）次。

到目前为止，我想到了以下代码：

public static double exponentiate(double x, int n) {
    counter++; 
    if (n == 0) {
        return 1.0;
    } else if (n == 1) {
        return x;
    } else {
        if (n % 2 == 0) {
            n = n-(n-1);
        } else {
            n = ((n-1) / 2) + n;
        }
        return ((x * x) * exponentiate(x, n - (n / 2)));
    }
}

但是不知何故，它仅适用于奇数n，而不适用于偶数n。

有人可以帮忙吗？

谢谢！

zenwraight：

我认为您可以O(logn)通过exponentiate(x,n/2)一次计算并使用它来优化运行上述方法。

像这样的东西：

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

希望这可以帮助！

本文收集自互联网，转载请注明来源。

如有侵权，请联系 [email protected] 删除。