Leetcode中问题编号50的StackOverFlow错误

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;
}