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

作者: mikemagic88 (Mikemagic88)   2018-07-12 15:22:57
開發平台(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)
把結果先存起來 再去做遞迴
但我不知道怎麼做
作者: idiont (supertroller)   2018-07-16 12:40:00
上面推文有講到dfs遞迴深度只要n層https://ideone.com/efWi43
作者: jerryh001   2018-07-12 15:25:00
改成迴圈
作者: Neisseria (Neisseria)   2018-07-12 15:38:00
可以調 stack size 嗎? Windows 預設 stack size 較小沒看到敘述,不好意思...
作者: sarafciel (Cattuz)   2018-07-12 16:33:00
編譯帶-O2試試 VC++應該有tail recursion?
作者: cutekid (可愛小孩子)   2018-07-12 17:25:00
不知道是怎樣的題目呢?方便敘述一下嗎^_^
作者: MOONRAKER (㊣牛鶴鰻毛人)   2018-07-12 17:32:00
你的tab寬度好多種 有2, 4, 6, 8 *_*
作者: bluesoul (忙死你老爸)   2018-07-12 17:53:00
增加stack size
作者: moebear (萌熊)   2018-07-12 19:39:00
應該只要n層吧
作者: cutekid (可愛小孩子)   2018-07-12 21:25:00
看來是要列出 c(9,n) * n! 的所有結果
作者: cphe (魔鬼藏在垃圾筒裡)   2018-07-12 21:44:00
你這做法不是這題用遞迴的精神,n層就應該可解決才是先假設n-1已經排列好,再去排第n位~ 然後設終止條件
作者: TitanEric (泰坦)   2018-07-12 23:04:00
樓上感覺是正解
作者: sarafciel (Cattuz)   2018-07-12 23:21:00
原PO這樣寫就很像廣先搜索,展開到最後stack才會開始收要像cphe大講的那樣做深先遞回,stack才會有借有還
作者: oToToT (屁孩)   2018-07-14 18:10:00
自己做stack模擬呢?
作者: yvb   2018-07-14 20:26:00
就如4F的說法, 原Po程式應該有tail recursion,照理說開最佳化後, 可能讓 stack 不成長, 但實測仍會爆掉;但若把SNum變為全域變數,即doPerm()外宣告string SNum;在doPerm()中改為sNum = "";則-O2後執行就不會爆掉;即使改寫為C, string sNum改為char sNum[20]等等, 情況相同;另解,把有關sNum算出iNum部分另拉函數,讓doPerm()沒sNum亦可.(使用的編譯器:g++/gcc 4.6.3)也許我用的編譯器無法正常處理tail recursion?
作者: AstralBrain   2018-07-14 21:44:00
用clang試了一下 想發動tail recursion要改兩個地方1. string放到global, 不然destructor會有影響2. function全部宣告成static (這我不知道為什麼)好像要static才會被最佳化update: g++5.4不用加static
作者: flysonics (飛音)   2018-07-15 00:37:00
最好的解法就是重構不要用遞迴明明知道stack資源可能不夠 就不要冒險用這個寫法 到時候還要東擠西擠的在那邊空間優化 這豈不是給自己添麻煩嗎
作者: ronin728 (浪人)   2018-07-15 14:01:00
跳床
作者: Killercat (殺人貓™)   2018-07-15 15:30:00
Stack overflow解法很少, 一是從gcc/linker下手,setrlimit()/--split-stack/-stack-size二就是在近一步降低function內的stack size最後也是最常見的,寫成迴圈吧...另外老師如果給出解法 請務必讓我們知道一下怎麼解 XD不過腦筋急轉彎一下,可以把本來該存stack的放到global的heap,global new一個能自動增長的容器(string就是)把所有東西都往裡面塞

Links booklink

Contact Us: admin [ a t ] ucptt.com