V2EX = way to explore
V2EX 是一个关于分享和探索的地方
现在注册
已注册用户请  登录
Sponsored by
LinkedIn
2000 个不用坐班的远程好工作在召唤你 · 弹性上班不打卡,工作和生活都能拥有
2000 个不用坐班的全球远程工作,帮助 V2EX 的小伙伴开启全新的工作方式。
Promoted by LinkedIn
andyJado
V2EX  ›  程序员

我写了一个递归函数, 能精准预防栈溢出吗?

  •  
  •   andyJado ·
    AndyJado · 44 天前 · 2162 次点击
    这是一个创建于 44 天前的主题,其中的信息可能已经有所发展或是发生改变。

    单纯的想知道我这个递归结构嵌套了多少个自己:

        fn layer(&self) -> usize {
            let orin = self.origin.as_ref();
            match orin {
                Some(itn) => itn.layer() + 1,
                None => 1,
            }
        }
    

    然而这个结构一到 8300 层就栈溢出了.

    第 1 条附言  ·  44 天前

    感谢两位前辈手把手教, 终贴:

    • 写成while loop直接有效,benchmark结果花费时间一致

    • 我这个函数ddpp就能改成尾递归了:

        fn layer(&self) -> usize {
            let orin = self.origin.as_ref();
            match orin {
                None => 1,
                Some(itn) => 1 + itn.layer(),
            }
        }
    

    芜湖

    第 2 条附言  ·  44 天前

    其实改一个字就可以了, 艹.

        fn layer(&self) -> usize {
            let orin = self.origin.as_ref();
            match orin {
                Some(itn) => 1 + itn.layer(),
                None => 1,
            }
        }
    
    14 条回复    2022-08-11 20:36:45 +08:00
    kenvix
        1
    kenvix  
       44 天前   ❤️ 1
    先查询一下栈空间是多大,然后每个调用帧占多少,除一下就能估测了
    IMXT
        2
    IMXT  
       44 天前 via iPhone   ❤️ 1
    写成尾递归就好啦
    Mistwave
        3
    Mistwave  
       44 天前 via iPhone
    停机问题
    newmlp
        4
    newmlp  
       44 天前
    所有递归都可以用循环替换
    duke807
        5
    duke807  
       44 天前 via Android   ❤️ 1
    我写 MCU C 代码,会在栈底部写一些特定的 patten 数据,定期检查这些 patten 有没有被修改,从而知道有没有溢出
    PTLin
        6
    PTLin  
       44 天前   ❤️ 1
    ```rust
    struct A {
    origin: Option<Box<A>>,
    }
    impl A {
    fn layer(&self) -> usize {
    let mut p = self;
    let mut count = 1;
    while let Some(itn) = &p.origin {
    count += 1;
    p = &*itn
    }
    count
    }
    ```
    这样不就完事了?
    lmshl
        7
    lmshl  
       44 天前

    从汇编结果看,对于你这个函数,O2 级别的优化足以替换成尾递归(迭代)实现了。
    你可以手动改成尾递归,让它在任何优化下都能正常工作,或者甩手交给编译器去做
    andyJado
        8
    andyJado  
    OP
       44 天前
    @PTLin
    感谢!
    确实没想到这么写.
    if, for, while 总是能避免就避免, 就像当初扔掉鼠标一样, 哈哈

    @lmshl
    您的回复对我直接就是一个启发式的解决了问题.
    PTLin
        9
    PTLin  
       44 天前
    @andyJado 你当这是 haskell 吗?还避免 if while ,你在 rust 里计算递归结构长度就算有优化也不能考虑用递归算啊
    lxdlam
        10
    lxdlam  
       44 天前   ❤️ 1
    尾递归跟迭代没有任何直接联系。

    - 可以把尾递归优化成迭代并不意味着常规递归不能被优化成迭代: https://stackoverflow.com/questions/54686395/how-can-modern-compiler-optimization-convert-recursion-into-returning-a-constant
    - 可以把尾递归优化成迭代同样不意味着尾递归一定会被优化成迭代: http://neopythonic.blogspot.com/2009/04/final-words-on-tail-calls.html
    lmshl
        11
    lmshl  
       44 天前   ❤️ 1
    @andyJado llvm 能把非尾递归优化成尾递归也吓到我了。
    当然实际应用中更建议手动写成尾递归形式,以保证 llvm 在任何优化下都可以生成迭代指令
    毕竟过于复杂的非尾递归循环,谁也不敢保证编译器是否认得出来
    andyJado
        12
    andyJado  
    OP
       44 天前
    @PTLin
    恕我愚笨.. 不是写成尾递归就可以了吗? 我 append 到上面了👆
    PTLin
        13
    PTLin  
       44 天前   ❤️ 2
    @andyJado 你有什么保证保证编译器一定会把你的递归优化成循环,没有这种保证就老老实实的写循环
    andyJado
        14
    andyJado  
    OP
       44 天前
    @PTLin
    好的老师!
    关于   ·   帮助文档   ·   API   ·   FAQ   ·   我们的愿景   ·   广告投放   ·   感谢   ·   实用小工具   ·   1714 人在线   最高记录 5497   ·     Select Language
    创意工作者们的社区
    World is powered by solitude
    VERSION: 3.9.8.5 · 43ms · UTC 17:18 · PVG 01:18 · LAX 10:18 · JFK 13:18
    Developed with CodeLauncher
    ♥ Do have faith in what you're doing.