递归实现的pow(x, n)函数为何在n较大时引发栈溢出？

嘿，这个问题我之前踩过同款坑！咱们先拆解下你的代码逻辑：你写的pow函数用的是线性递归——每次调用都会触发pow(x, n-1)，比如当n是10000的时候，程序要连续递归调用10000次这个函数。

你得知道，每一次函数递归调用，都会在程序的栈内存里创建一个「调用帧」，里面要存返回地址、局部变量这些信息。而程序的栈空间是有限的（一般也就几MB大小），哪怕每个调用帧只占几十字节，几万次调用下来直接就把栈空间撑爆了，这就是你遇到的栈溢出问题。

那怎么解决这个问题？咱们可以换用**快速幂（分治递归）**的思路，把递归深度从O(n)直接降到O(log₂n)，哪怕n是1e9，递归次数也才30次左右，完全不会给栈造成压力。

修改后的代码可以这样写：

class Solution {
public:
    double myPow(double x, int n) {
        long long exp = n;
        if (exp < 0) {
            x = 1 / x;
            exp = -exp;
        }
        return pow(x, exp);
    }

    double pow(double x, long long n) {
        if (n == 0) return 1;
        // 先计算一半规模的结果
        double half_result = pow(x, n / 2);
        // 偶数次幂：一半结果乘自己
        if (n % 2 == 0) {
            return half_result * half_result;
        } else {
            // 奇数次幂：多乘一次底数x
            return half_result * half_result * x;
        }
    }
};

简单说下优化逻辑：计算x^{n时，不用傻乎乎地一步步乘x，而是把问题拆成两半——比如x}10 = (x⁵⁾2，x^5 = (x²⁾2 * x，每一次递归都把问题规模砍半，递归层数直接变成对数级别，栈空间的使用瞬间就降到了可以忽略的程度。

另外提一句，你处理n为负数的部分是对的，把int转成long long避免了溢出问题，这部分没毛病~

内容来源于stack exchange