Leetcode中问题编号50的堆栈溢出错误

Question

对于下面的输入，我得到一个StackOverflow错误。你们能帮我解释一下吗，以及如何在我的代码中解决这个问题。

 System.out.println(myPow(0.00001,2147483647));  

 public static double myPow(double x, int n) {
         
        return helperPow(x,n,1);
        }


     
     private static double helperPow(double x, int n,double d) {
         if(n == 0) {
             return d;
         }
         
         if(n < 0) {
             return  helperPow(x,++n, d/x);
         }
         
         return helperPow(x, --n, d*x); 
         
     }

Answer 1

使用您当前的方法，递归的层数将等于n，因此它肯定会导致StackOverflow异常，因为它需要相当大的堆栈空间。

请注意，如果n是偶数，x^n=（x^（n/2））*（x^（n/2））。

如果n是奇数，x^n=（x^（n/2））*（x^（n/2））*x。

因此，您可以将递归级别的数量减少到log（n），即使n很大，也绝对不会导致Stackoverflow异常（在您的情况下，n为2147483647，需要31次递归）：

    public double myPow(double x, int n) {
        return n >= 0 ? helperPow(x, n) : 1.0 / helperPow(x, -n);
    }
    public double helperPow(double x, long n) {
        if (n == 0) {
            return 1.0;
        }
        double y = helperPow(x, n / 2);
        return n % 2 == 0 ? y * y : y * y * x;
    }