递归实现pow(x,n)的C++代码出现运行时错误，求原因

先看你提供的代码：

class Solution {
public:
    double myPow(double x, int n) 
    {
        if(n==0)
            return 1;
        return x*myPow(x,n-1);    
    }
};

这段代码触发运行时错误主要有三个核心原因：

• 负数n导致无限递归：当传入的n是负数时，比如n=-1，递归调用会执行myPow(x, -2)，接着是myPow(x, -3)……永远不会触发n==0的终止条件，无限递归会耗尽栈空间，直接引发栈溢出错误。
• int最小值的溢出问题：C++中int的取值范围通常是-2^31到2^31-1，当n等于INT_MIN（即-2147483648）时，执行n-1会触发整数溢出，得到的结果是2147483647（补码溢出的特性），这会让递归方向完全错乱，同样无法终止，最终导致栈溢出。
• 正数n的递归深度超限：就算n是正数，比如取最大值2^31-1，递归深度会达到2000多万次，而程序的栈空间通常只有几MB，根本无法容纳这么多层的递归调用，最终还是会因为栈空间耗尽触发运行时错误。

如果要修复这个问题，可以先把n转换成long long类型避免溢出，同时处理负数情况（把x取倒数，n取绝对值），再用快速幂的思路减少递归深度，示例代码如下：

class Solution {
public:
    double myPow(double x, int n) {
        long long N = n;
        if (N < 0) {
            x = 1 / x;
            N = -N;
        }
        return fastPow(x, N);
    }
    
    double fastPow(double x, long long n) {
        if (n == 0) {
            return 1.0;
        }
        double half = fastPow(x, n / 2);
        return n % 2 == 0 ? half * half : half * half * x;
    }
};

内容的提问来源于stack exchange，提问作者M Tarun