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

Question

我想更改此求幂方法(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);
    }
}

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

到目前为止，我想出了这段代码:

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。

有人可以帮忙吗？

谢谢!

Answer 1

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

类似这样的:-

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

希望这有帮助!