作者mikemagic88 (Mikemagic88)
看板C_and_CPP
標題[問題] 遞迴 stack overflow怎麼解決?
時間Thu Jul 12 15:22:57 2018
開發平台(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://webptt.com/m.aspx?n=bbs/C_and_CPP/M.1531380180.A.B74.html
1F：推 jerryh001: 改成迴圈 07/12 15:25
不好意思 這題被規定要用遞迴做 QQ
2F：推 Neisseria: 可以調 stack size 嗎？ Windows 預設 stack size 較小 07/12 15:38
3F：→ Neisseria: 沒看到敘述，不好意思... 07/12 15:39
4F：→ sarafciel: 編譯帶-O2試試 VC++應該有tail recursion? 07/12 16:33
5F：推 cutekid: 不知道是怎樣的題目呢？方便敘述一下嗎^_^ 07/12 17:25
輸入數字n 1<=n<=9
做出n位數的排列
例如3 -> 123 ~ 987
我的做法是123 一直+1直到999
不重複的再印出來
遞迴+1的部分
6F：→ MOONRAKER: 你的tab寬度好多種 有2, 4, 6, 8 ＊_＊ 07/12 17:32
好像是複製貼上的問題
7F：→ bluesoul: 增加stack size 07/12 17:53
這是我目前做的, 不知道有沒有其他做法呢
※ 編輯: mikemagic88 (61.228.138.202), 07/12/2018 18:02:32
8F：推 moebear: 應該只要n層吧 07/12 19:39
9F：推 cutekid: 看來是要列出 c(9,n) * n! 的所有結果 07/12 21:25
10F：推 cphe: 你這做法不是這題用遞迴的精神，n層就應該可解決才是 07/12 21:44
11F：→ cphe: 先假設n-1已經排列好，再去排第n位~ 然後設終止條件 07/12 21:45
12F：推 TitanEric: 樓上感覺是正解 07/12 23:04
13F：→ sarafciel: 原PO這樣寫就很像廣先搜索，展開到最後stack才會開始收 07/12 23:21
14F：→ sarafciel: 要像cphe大講的那樣做深先遞回，stack才會有借有還 07/12 23:22
15F：推 oToToT: 自己做stack模擬呢？ 07/14 18:10
16F：推 yvb: 就如4F的說法, 原Po程式應該有tail recursion, 07/14 20:26
17F：→ yvb: 照理說開最佳化後, 可能讓 stack 不成長, 但實測仍會爆掉; 07/14 20:29
18F：→ yvb: 但若把SNum變為全域變數,即doPerm()外宣告string SNum; 07/14 20:34
19F：→ yvb: 在doPerm()中改為sNum = "";則-O2後執行就不會爆掉; 07/14 20:36
20F：→ yvb: 即使改寫為C, string sNum改為char sNum[20]等等, 情況相同; 07/14 20:38
21F：→ yvb: 另解,把有關sNum算出iNum部分另拉函數,讓doPerm()沒sNum亦可. 07/14 20:47
22F：→ yvb: (使用的編譯器:g++/gcc 4.6.3) 07/14 20:49
23F：→ yvb: 也許我用的編譯器無法正常處理tail recursion? 07/14 20:51
24F：推 AstralBrain: 用clang試了一下 想發動tail recursion要改兩個地方 07/14 21:44
25F：→ AstralBrain: 1. string放到global, 不然destructor會有影響 07/14 21:44
26F：→ AstralBrain: 2. function全部宣告成static (這我不知道為什麼) 07/14 21:45
27F：→ AstralBrain: 好像要static才會被最佳化 07/14 21:45
28F：推 AstralBrain: update: g++5.4不用加static 07/14 21:50
29F：→ flysonics: 最好的解法就是重構不要用遞迴 07/15 00:37
30F：→ flysonics: 明明知道stack資源可能不夠 就不要冒險用這個寫法 到 07/15 00:39
31F：→ flysonics: 時候還要東擠西擠的在那邊空間優化 這豈不是給自己添 07/15 00:39
32F：→ flysonics: 麻煩嗎 07/15 00:39
33F：推 ronin728: 跳床 07/15 14:01
34F：推 Killercat: Stack overflow解法很少, 一是從gcc/linker下手， 07/15 15:30
35F：→ Killercat: setrlimit()/--split-stack/-stack-size 07/15 15:30
36F：→ Killercat: 二就是在近一步降低function內的stack size 07/15 15:31
37F：→ Killercat: 最後也是最常見的，寫成迴圈吧... 07/15 15:31
38F：→ Killercat: 另外老師如果給出解法 請務必讓我們知道一下怎麼解 XD 07/15 15:31
39F：→ Killercat: 不過腦筋急轉彎一下，可以把本來該存stack的放到global 07/15 15:32
40F：→ Killercat: 的heap，global new一個能自動增長的容器(string就是) 07/15 15:32
41F：→ Killercat: 把所有東西都往裡面塞 07/15 15:33
42F：推 idiont: 上面推文有講到dfs遞迴深度只要n層 07/16 12:40