作者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/cn.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