使递归效率更高的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);
    }
}

我想更改该方法以使其更有效，因此该方法在不使用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。

有人可以帮忙吗？

谢谢！

Answer 1

我不知道这是否是您要搜索的解决方案，但这是在O（log（n））时间内执行幂运算的算法的示例

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