[問題] 遞迴 stack overflow怎麼解決?

看板C_and_CPP作者 (Mikemagic88)時間5年前 (2018/07/12 15:23), 5年前編輯推噓14(14推 0噓 29→)
留言43則, 16人參與, 5年前最新討論串1/1
開發平台(Platform): (Ex: Win10, Linux, ...) Windows 編譯器(Ex: GCC, clang, VC++...)+目標環境(跟開發平台不同的話需列出) Dev cpp 額外使用到的函數庫(Library Used): (Ex: OpenGL, ...) 無 問題(Question)： 遞迴數字很大, 會stackoverflow 餵入的資料(Input)： 1-9 預期的正確結果(Expected Output)： [1] 1, 2 [2] 1, 3 [3] 1, 4 [4] 1, 5 .... [87] 9, 8 錯誤結果(Wrong Output)： 到一定的數字就會stack overflow 我只會用-Wl,-stack,5000000000解決 程式碼(Code)：(請善用置底文網頁, 記得排版，禁止使用圖檔) http://codepad.org/gwTDYbwW 補充說明(Supplement)： 程式沒有寫錯 我想問怎麼解決stack overflow的問題 我有想過要做到一定程度(例如數字<2000) 把結果先存起來 再去做遞迴 但我不知道怎麼做 -- ※ 發信站: 批踢踢實業坊(ptt.cc), 來自: 61.228.138.202 ※ 文章網址: https://www.ptt.cc/bbs/C_and_CPP/M.1531380180.A.B74.html
推
07/12 15:25, 5年前 , 1F
改成迴圈
07/12 15:25, 1F
不好意思 這題被規定要用遞迴做 QQ
推
07/12 15:38, 5年前 , 2F
可以調 stack size 嗎？ Windows 預設 stack size 較小
07/12 15:38, 2F
→
07/12 15:39, 5年前 , 3F
沒看到敘述，不好意思...
07/12 15:39, 3F
→
07/12 16:33, 5年前 , 4F
編譯帶-O2試試 VC++應該有tail recursion?
07/12 16:33, 4F
推
07/12 17:25, 5年前 , 5F
不知道是怎樣的題目呢？方便敘述一下嗎^_^
07/12 17:25, 5F
輸入數字n 1<=n<=9 做出n位數的排列 例如3 -> 123 ~ 987 我的做法是123 一直+1直到999 不重複的再印出來 遞迴+1的部分
→
07/12 17:32, 5年前 , 6F
你的tab寬度好多種 有2, 4, 6, 8 ＊_＊
07/12 17:32, 6F
好像是複製貼上的問題
→
07/12 17:53, 5年前 , 7F
增加stack size
07/12 17:53, 7F
這是我目前做的, 不知道有沒有其他做法呢 ※ 編輯: mikemagic88 (61.228.138.202), 07/12/2018 18:02:32
推
07/12 19:39, 5年前 , 8F
應該只要n層吧
07/12 19:39, 8F
推
07/12 21:25, 5年前 , 9F
看來是要列出 c(9,n) * n! 的所有結果
07/12 21:25, 9F
推
07/12 21:44, 5年前 , 10F
你這做法不是這題用遞迴的精神，n層就應該可解決才是
07/12 21:44, 10F
→
07/12 21:45, 5年前 , 11F
先假設n-1已經排列好，再去排第n位~ 然後設終止條件
07/12 21:45, 11F
推
07/12 23:04, 5年前 , 12F
樓上感覺是正解
07/12 23:04, 12F
→
07/12 23:21, 5年前 , 13F
原PO這樣寫就很像廣先搜索，展開到最後stack才會開始收
07/12 23:21, 13F
→
07/12 23:22, 5年前 , 14F
要像cphe大講的那樣做深先遞回，stack才會有借有還
07/12 23:22, 14F
推
07/14 18:10, 5年前 , 15F
自己做stack模擬呢？
07/14 18:10, 15F
推
07/14 20:26, 5年前 , 16F
就如4F的說法, 原Po程式應該有tail recursion,
07/14 20:26, 16F
→
07/14 20:29, 5年前 , 17F
照理說開最佳化後, 可能讓 stack 不成長, 但實測仍會爆掉;
07/14 20:29, 17F
→
07/14 20:34, 5年前 , 18F
但若把SNum變為全域變數,即doPerm()外宣告string SNum;
07/14 20:34, 18F
→
07/14 20:36, 5年前 , 19F
在doPerm()中改為sNum = "";則-O2後執行就不會爆掉;
07/14 20:36, 19F
→
07/14 20:38, 5年前 , 20F
即使改寫為C, string sNum改為char sNum[20]等等, 情況相同;
07/14 20:38, 20F
→
07/14 20:47, 5年前 , 21F
另解,把有關sNum算出iNum部分另拉函數,讓doPerm()沒sNum亦可.
07/14 20:47, 21F
→
07/14 20:49, 5年前 , 22F
(使用的編譯器:g++/gcc 4.6.3)
07/14 20:49, 22F
→
07/14 20:51, 5年前 , 23F
也許我用的編譯器無法正常處理tail recursion?
07/14 20:51, 23F
推
07/14 21:44, 5年前 , 24F
用clang試了一下 想發動tail recursion要改兩個地方
07/14 21:44, 24F
→
07/14 21:44, 5年前 , 25F
1. string放到global, 不然destructor會有影響
07/14 21:44, 25F
→
07/14 21:45, 5年前 , 26F
2. function全部宣告成static (這我不知道為什麼)
07/14 21:45, 26F
→
07/14 21:45, 5年前 , 27F
好像要static才會被最佳化
07/14 21:45, 27F
推
07/14 21:50, 5年前 , 28F
update: g++5.4不用加static
07/14 21:50, 28F
→
07/15 00:37, 5年前 , 29F
最好的解法就是重構不要用遞迴
07/15 00:37, 29F
→
07/15 00:39, 5年前 , 30F
明明知道stack資源可能不夠 就不要冒險用這個寫法 到
07/15 00:39, 30F
→
07/15 00:39, 5年前 , 31F
時候還要東擠西擠的在那邊空間優化 這豈不是給自己添
07/15 00:39, 31F
→
07/15 00:39, 5年前 , 32F
麻煩嗎
07/15 00:39, 32F
推
07/15 14:01, 5年前 , 33F
跳床
07/15 14:01, 33F
推
07/15 15:30, 5年前 , 34F
Stack overflow解法很少, 一是從gcc/linker下手，
07/15 15:30, 34F
→
07/15 15:30, 5年前 , 35F
setrlimit()/--split-stack/-stack-size
07/15 15:30, 35F
→
07/15 15:31, 5年前 , 36F
二就是在近一步降低function內的stack size
07/15 15:31, 36F
→
07/15 15:31, 5年前 , 37F
最後也是最常見的，寫成迴圈吧...
07/15 15:31, 37F
→
07/15 15:31, 5年前 , 38F
另外老師如果給出解法 請務必讓我們知道一下怎麼解 XD
07/15 15:31, 38F
→
07/15 15:32, 5年前 , 39F
不過腦筋急轉彎一下，可以把本來該存stack的放到global
07/15 15:32, 39F
→
07/15 15:32, 5年前 , 40F
的heap，global new一個能自動增長的容器(string就是)
07/15 15:32, 40F
→
07/15 15:33, 5年前 , 41F
把所有東西都往裡面塞
07/15 15:33, 41F
推
07/16 12:40, 5年前 , 42F
上面推文有講到dfs遞迴深度只要n層
07/16 12:40, 42F
→
07/16 12:40, 5年前 , 43F
07/16 12:40, 43F
‣ 更多 mikemagic88 的文章
文章代碼(AID): #1RHm7Kjq (C_and_CPP)