减少pow递归方法的递归调用？

Question

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

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).