递归实现LeetCode Pow(x,n)遇栈溢出问题及优化方案咨询

这是一道计算x的n次幂的算法题，n的取值范围为 -2^31 ≤ n ≤ 2^31-1。

遇到的错误 #

当测试用例为x=0.00001、n=2147483647时，递归代码触发栈溢出，错误信息如下：

Error:
AddressSanitizer:DEADLYSIGNAL
31ERROR: AddressSanitizer: stack-overflow on address 0x7ffe5053aff8 (pc 0x000000343a6a bp 0x7ffe5053b010 sp 0x7ffe5053b000 T0)
31ABORTING

初始递归代码 #

double myPow(double x, long long n) {
         double res;
         // long long nn=abs(n);
        // BC
        if(n==0)
            return 1;
        if(x==0) 
            return 0;
        
             res=myPow(x,abs(n)-1);
             return n<0?1/(x*res):x*res;
}

疑问与优化代码 #

已将n的类型从int改为long long避免溢出，想了解还有哪些解决溢出的方法；另外编写了优化版本的代码，希望得到进一步改进建议：

double myPow(double x, int n) {
         double res;
         long long nn=abs(n);
        // BC
        if(n==0)
            return 1;
        if(x==0) 
            return 0;
        
        if(nn%2==0){
            res=myPow(x,nn/2);
            res=res*res;
            return n<0?1/res:res;
        }
        else {
             res=myPow(x,nn-1);
             return n<0?1/(x*res):x*res;
        }
}       

栈溢出的核心原因 #

初始代码是线性递归逻辑，每次递归仅将n减1，当n取最大值2147483647时，递归深度会达到21亿级，远远超出程序栈的容量限制，必然触发栈溢出。优化版采用了快速幂的分治思路，递归深度降至log2(2^31)≈31层，已经解决了栈溢出问题，但仍有优化空间。

其他避免n溢出的方法 #

1. 单独处理n=-2^31的特殊情况：int类型的-2^31取绝对值会超出int的最大值（2^31-1），因此必须转成long long处理。除了你当前用long long nn=abs(n)的方式，也可以提前判断并转换：

   if (n == INT_MIN) {
       x *= x;
       n /= 2;
   }
   

2. 直接将函数参数n设为long long：把函数入参n的类型定义为long long，无需在函数内部做类型转换，从根源避免溢出风险。

优化版代码的改进建议 #

1. 优化奇数分支的递归逻辑：当前奇数分支调用myPow(x, nn-1)会多一次递归，可改为和偶数分支一致的单次递归：

   else {
       res = myPow(x, nn/2);
       return n < 0 ? 1/(x * res * res) : x * res * res;
   }
   

   这样奇数情况的递归深度和偶数保持一致，效率更高。
2. 移除冗余判断或调整顺序：x==0的判断可以和特殊值判断合并，比如先处理x=1直接返回1、x=-1根据n奇偶返回1或-1，再处理x=0的情况，减少不必要的计算。
3. 改用迭代实现快速幂：如果担心递归栈的潜在问题（31层其实完全安全），可以改成迭代版本，彻底规避栈溢出：

   double myPow(double x, int n) {
       long long nn = n;
       if (nn < 0) {
           x = 1 / x;
           nn = -nn;
       }
       double result = 1.0;
       while (nn > 0) {
           if (nn % 2 == 1) {
               result *= x;
           }
           x *= x;
           nn /= 2;
       }
       return result;
   }
   

4. 提前处理特殊输入：比如x=1时直接返回1，x=-1时根据n的奇偶性返回1或-1，这些情况提前判断可以跳过后续所有计算步骤。

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