java - 减少对pow递归方法的递归调用？

Question

有一个关于如何减少 pow 方法的 self 实现的递归调用量的问题。这是我写的，可以改进吗？

public static int pow(double a, int b) {
    boolean isNegative = false;

    if(b < 0) {
        isNegative = true;
    }

    if(b == 0) {
        return 1;
    } 
    else if(b == 1) {
        return (isNegative ? (1 / b) : b);
    }

    return (isNegative ? ((1 / b) * (1 / b) * pow(a, b + 2)) : (b * b * pow(a, b - 2)));
}

Answer 1

是的，可以改进。

这样想:

• 如果 b 是偶数，则 a^b = a^(b/2) * a^(b/2)。
• 如果 b 为奇数，则 a^b = a^(b/2) * a^(b/2) * a(其中/表示整数除法)。

代码(大脑编译、咖啡尚未开始等):

public static double pow(double a, int b) {
    if (b < 0)
        return 1 / pow(a, -b);
    if (b == 0)
        return 1;
    double halfPow = pow(a, b/2);
    if (b % 2 == 0)
        return halfPow * halfPow;
    else
        return halfPow * halfPow * a;
}

这为您提供了 O(log b) 递归调用，而不是您的解决方案中的 O(n)。