本文详解 LeetCode 中实现 myPow 函数时因递归深度过大或边界判断失效导致的 StackOverflowError，重点分析 n = -2147483648 等极端用例的成因，并提供安全、高效、符合约束的递归快速幂实现方案。
本文详解 leetcode 中实现 `mypow` 函数时因递归深度过大或边界判断失效导致的 stackoverflowerror，重点分析 `n = -2147483648` 等极端用例的成因，并提供安全、高效、符合约束的递归快速幂实现方案。
在实现快速幂（Fast Power）算法时，递归写法虽简洁，但极易因终止条件设计不当或整数溢出引发无限递归而触发 StackOverflowError。原代码中看似设置了 if (x 10000) return 0; 作为兜底，实则完全无效——因为该条件依赖 x 的绝对值，而 positivePow 中 x * x 在首次调用后可能迅速爆炸（如 x = 2.0, n = -2147483648），但更致命的问题在于：n = -2147483648（即 Integer.MIN_VALUE）取负后仍为自身，导致 positivePow(1/x, -n) 中 -n 溢出，传入 positivePow 的 n 值仍是负数，从而绕过所有 n == 1 或 n == 0 的终止分支，陷入无限递归。
根本原因有三：
- ❌ 整数溢出未防护：
int n = -2147483648，执行-n会溢出回−2147483648（补码表示下无对应正数），使positivePow(1/x, -n)实际调用positivePow(1/x, -2147483648)，而n始终不满足n == 1或n == 0； - ❌ 终止条件逻辑错位：
x的范围检查（x ）发生在递归深层，且与 <code>n无关，无法阻止递归深度增长； - ❌ 除零风险隐藏：原逻辑
return 1 / positivePow(x, -n)在positivePow返回0时将引发1/0.0 → Infinity，虽不直接报错，但破坏数值稳定性，且掩盖了底层递归异常。
✅ 正确解法需从类型、逻辑、结构三方面重构：
-
升级
n为long类型，彻底规避Integer.MIN_VALUE取负溢出问题； - 统一递归入口，消除冗余分支，采用经典二分递归结构：奇偶分离 + 平方降幂；
-
精简终止条件：仅保留
n == 0 → 1和n == 1 → x，无需对x做非常规截断（题目已保证|x| ，且 <code>|x^n| ≤ 1e4，数值本身可控）； -
避免中间除法，直接通过
n 分支调用 <code>myPow(1/x, -n)，确保n始终非负进入核心递归。
以下是生产就绪的参考实现：
public double myPow(double x, int n) {
return myPow(x, (long) n); // 安全转型，防止 int 溢出
}
private double myPow(double x, long n) {
if (n == 0) return 1.0;
if (n < 0) return myPow(1.0 / x, -n);
if (n == 1) return x;
if (n % 2 == 1) {
return x * myPow(x * x, n / 2); // 奇数：x * (x²)^(n/2)
} else {
return myPow(x * x, n / 2); // 偶数：(x²)^(n/2)
}
}⚠️ 关键注意事项：
- 不要使用
int n直接参与负数取反运算，必须先转为long； -
n / 2在long下是整除（向下取整），与n % 2 == 1配合可精确覆盖所有情况； -
x * x可能增大，但题目约束|x| 且 <code>|x^n| ≤ 1e4，结合指数快速衰减（尤其n大时x接近 0 或|x| ），实际不会溢出 <code>double范围； - 该实现时间复杂度为
O(log |n|)，空间复杂度为O(log |n|)（递归栈深），完全满足 LeetCode 性能要求。
综上，栈溢出并非“终止条件没写”，而是终止条件被溢出绕过、递归逻辑未覆盖边界类型所致。抓住 int 溢出本质，升维处理 n，并回归快速幂标准范式，即可一劳永逸解决问题。
