LeetCode myPow实现遇栈溢出：指定终止条件对n=-2147483648失效

问题根源 #

当测试用例为x=2.00000、n=-2147483648时，栈溢出的核心原因是int类型溢出：

• Java中int的取值范围是[-2^31, 2^31-1]，当n=-2147483648（即-2^31）时，-n的结果是2^31，超出了int的最大值，会溢出为-2147483648（补码特性）。
• 此时传入positivePow的n仍是负数，而positivePow的终止条件仅判断n==1，负数会导致递归无限调用，最终栈溢出。
• 你设置的x范围判断未生效，是因为递归还没走到该逻辑就已经因无限调用栈溢出了。

修复方案 #

1. 用long类型避免n的溢出 #

将n转换为long类型处理，确保取反操作不会溢出。

2. 优化递归逻辑（可选但更高效） #

将奇数幂的递归逻辑从x * positivePow(x, n-1)改为x * positivePow(x*x, (n-1)/2)，减少递归深度。

3. 移除无效的x范围判断 #

题目约束明确x^n的范围在[-10^4, 10^4]，且x的范围是[-100, 100]，该判断无法提前终止有效递归，反而可能干扰正常计算。

修复后的代码 #

class Solution {
    public double myPow(double x, int n) {
        // 转换为long避免n=-2^31时取反溢出
        long ln = n;
        if (x == 1) {
            return 1;
        }
        if (ln == 0) {
            return 1;
        }
        if (ln > 0) {
            return positivePow(x, ln);
        } else {
            return positivePow(1 / x, -ln);
        }
    }

    public double positivePow(double x, long n) {
        if (n == 1) {
            return x;
        }
        if (n % 2 == 0) {
            return positivePow(x * x, n / 2);
        } else {
            // 优化奇数幂的递归逻辑，减少递归深度
            return x * positivePow(x * x, (n - 1) / 2);
        }
    }
}

额外说明 #

• 当n=-2^31时，转换为long后-ln就是合法的2^31，能正常进入positivePow处理正指数递归。
• 优化后的奇数幂逻辑将递归深度从O(n)降到O(log n)，不仅解决栈溢出，还大幅提升计算效率。

内容的提问来源于stack exchange，提问作者Anmol Agrawal