平台: Leetcode in C
Implement pow(x, n), which calculates x raised to the power n (i.e. xn).
在case myPow(0.00001,2147483647) 出現stack overflow的情況，
其實第二個參數不到INT_MAX就會overflow了。 請問是不是遞迴太深的緣故，要怎麼保證不會overflow?
謝謝
double myPow(double x, int n){
double output;
if(n>0)
{
if(n == 1 )
return x;
else
{
output = x*myPow(x,n-1);
}
}
else if(n == 0 )
return 1;
else
{
if(n == -1)
return 1/x;
else
output = (1/x)*myPow(x,n+1);
}
return output;
}
作者: yangerma (walkhorse) 2020-09-30 19:25:00
你這邊提到了兩種overflow，我還不確定你是不是把兩種搞混了。"stack overflow"就像你說的可能是遞迴過深的關係，至於多深叫過深跟runtime的系統設定、還有你的遞迴函數會吃多少記憶體有關。至於遞迴為什麼不能過深，跟遞迴在執行時是如何做到的有關，不知道的話值得去了解一下。另外你提到的跟INT_MAX有關的是整數的overflow，因為C語言裡int只能表達某個大小範圍內的整數，如果在拿int運算的過程中超過那個範圍，導致運算的結果不如預期。以上兩種overflow完全是兩回事，而這份程式碼看起來很可能是發生了第一種(stack overflow)。你可以數數看這個程式應該會遞迴幾層，以後就會知道這樣的深度是會導致stack overflow的。至於解決方法，最簡單的就是不要用遞迴ww