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

[andyJado]

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

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

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

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

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

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

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

芜湖

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

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

[kenvix]

先查询一下栈空间是多大，然后每个调用帧占多少，除一下就能估测了

[IMXT]

写成尾递归就好啦

[Mistwave]

停机问题

[newmlp]

所有递归都可以用循环替换

[duke807]

我写 MCU C 代码，会在栈底部写一些特定的 patten 数据，定期检查这些 patten 有没有被修改，从而知道有没有溢出

[PTLin]

```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]

从汇编结果看，对于你这个函数，O2 级别的优化足以替换成尾递归（迭代）实现了。
你可以手动改成尾递归，让它在任何优化下都能正常工作，或者甩手交给编译器去做

[andyJado]

@PTLin
感谢!
确实没想到这么写.
if, for, while 总是能避免就避免, 就像当初扔掉鼠标一样, 哈哈

@lmshl
您的回复对我直接就是一个启发式的解决了问题.

[PTLin]

@andyJado 你当这是 haskell 吗？还避免 if while ，你在 rust 里计算递归结构长度就算有优化也不能考虑用递归算啊

[lxdlam]

尾递归跟迭代没有任何直接联系。

- 可以把尾递归优化成迭代并不意味着常规递归不能被优化成迭代： 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]

@andyJado llvm 能把非尾递归优化成尾递归也吓到我了。
当然实际应用中更建议手动写成尾递归形式，以保证 llvm 在任何优化下都可以生成迭代指令
毕竟过于复杂的非尾递归循环，谁也不敢保证编译器是否认得出来

[andyJado]

@PTLin
恕我愚笨.. 不是写成尾递归就可以了吗? 我 append 到上面了👆

[PTLin]

@andyJado 你有什么保证保证编译器一定会把你的递归优化成循环，没有这种保证就老老实实的写循环

[andyJado]

@PTLin
好的老师!