作者anoymouse (沒有暱稱)
看板C_and_CPP
標題[問題] leetcode POW(n,x) stack overflow
時間Wed Sep 30 10:48:40 2020
平台: 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;
}
--
※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.230.161.136 (臺灣)
※ 文章網址: https://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1601434122.A.85E.html
※ 編輯: anoymouse (61.230.161.136 臺灣), 09/30/2020 10:51:23
1F：推 xiefengan: Google 快速冪 09/30 12:19
正在看 還在消化中 也許可以避免stack overflow。
2F：→ s90104123: INT_MAX看看？ 09/30 16:36
3F：推 yangerma: 你這邊提到了兩種overflow，我還不確定你是不是把兩種搞 09/30 19:25
4F：→ yangerma: 混了。 09/30 19:26
5F：→ yangerma: "stack overflow"就像你說的可能是遞迴過深的關係，至於 09/30 19:26
6F：→ yangerma: 多深叫過深跟runtime的系統設定、還有你的遞迴函數會吃 09/30 19:26
7F：→ yangerma: 多少記憶體有關。至於遞迴為什麼不能過深，跟遞迴在執行 09/30 19:26
8F：→ yangerma: 時是如何做到的有關，不知道的話值得去了解一下。 09/30 19:26
9F：→ yangerma: 另外你提到的跟INT_MAX有關的是整數的overflow，因為C語 09/30 19:26
10F：→ yangerma: 言裡int只能表達某個大小範圍內的整數，如果在拿int運算 09/30 19:26
11F：→ yangerma: 的過程中超過那個範圍，導致運算的結果不如預期。 09/30 19:26
12F：→ yangerma: 以上兩種overflow完全是兩回事，而這份程式碼看起來很可 09/30 19:26
13F：→ yangerma: 能是發生了第一種(stack overflow)。你可以數數看這個程 09/30 19:26
14F：→ yangerma: 式應該會遞迴幾層，以後就會知道這樣的深度是會導致stac 09/30 19:26
15F：→ yangerma: k overflow的。 09/30 19:26
16F：→ yangerma: 至於解決方法，最簡單的就是不要用遞迴ww 09/30 19:26
我這邊純粹在指stack overflow，會提到INT_MAX只是因為leetcode把第二個參數設成
INT_MAX，當然如果最終回傳直>INT_MAX可能也有問題，但目前主要是想先處理
stack overflow。
17F：推 alan23273850: 能用迴圈就不要用遞迴 09/30 19:51
18F：→ WPC001: 你這個為什麼一定要用遞迴? 09/30 22:58
是沒有一定要用遞迴 我一開始也是想用迴圈，但是我想看看別人是怎麼做的
發現該題的討論區通通都是用遞迴，就想說試試看遞迴。
※ 編輯: anoymouse (36.227.161.96 臺灣), 10/02/2020 12:05:12
19F：推 kingofsdtw: 別用recursive看看? recursive考試用而已 10/06 18:31
20F：→ kingofsdtw: 現實上一堆會變成地雷 10/06 18:31