[問題] leetcode POW(n,x) stack overflow

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