LeetCode第50题：实现myPow方法触发StackOverflowError问题求助

先看看你写的实现代码：

public static double myPow(double x, int n) { 
    return helperPow(x,n,1); 
} 
private static double helperPow(double x, int n,double d) { 
    if(n == 0) { 
        return d; 
    } 
    if(n < 0) { 
        return helperPow(x,++n, d/x); 
    } 
    return helperPow(x, --n, d*x); 
}

问题原因 #

你的递归思路是逐次累乘/累除：每次递归只把n的绝对值减1，然后更新结果d。当传入n=2147483647（也就是int类型的最大值）时，递归的深度会达到21亿多层！

Java的虚拟机栈空间是有限的（默认一般是几MB），每一次递归调用都会在栈里创建一个新的栈帧来存储局部变量、方法参数等信息。这么庞大的递归深度直接会把栈空间耗尽，自然就抛出StackOverflowError了。

而且还有个隐藏问题：如果传入n=-2147483648（int的最小值），++n之后会变成-2147483647，还是要递归21亿次，同样会栈溢出，而且因为int的范围限制，你没法直接把负数转成正数处理（-n会溢出）。

解决方案：用快速幂（二分法）优化递归 #

快速幂的核心思路是将指数二分，把时间复杂度从O(n)降到O(log₂n)，递归深度也会变成log₂(2^31)≈31层，完全不会触发栈溢出。

另外要注意处理int最小值的情况，因为-2147483648取反会溢出，所以可以先把n转成long类型来处理，避免溢出问题。

优化后的递归版代码如下：

public static double myPow(double x, int n) {
    // 把n转成long，避免int最小值取反溢出
    long exponent = n;
    return exponent >= 0 ? quickPow(x, exponent) : 1.0 / quickPow(x, -exponent);
}

private static double quickPow(double x, long n) {
    if (n == 0) {
        return 1.0;
    }
    // 二分递归：先算x^(n/2)
    double half = quickPow(x, n / 2);
    // 如果n是偶数，结果是half*half；如果是奇数，多乘一个x
    return n % 2 == 0 ? half * half : half * half * x;
}

如果不想用递归，也可以写迭代版的快速幂，同样高效且避免栈溢出：

public static double myPow(double x, int n) {
    long exponent = n;
    if (exponent < 0) {
        x = 1 / x;
        exponent = -exponent;
    }
    double result = 1.0;
    while (exponent > 0) {
        // 如果当前指数是奇数，先乘一次x
        if (exponent % 2 == 1) {
            result *= x;
        }
        // x平方，指数除以2
        x *= x;
        exponent /= 2;
    }
    return result;
}

这两个版本处理myPow(0.00001,2147483647)的时候，只会循环/递归30多次，完全不会有栈溢出的问题，计算效率也提升了几个数量级。

内容的提问来源于stack exchange，提问作者mohammed fahimullah