单纯的想知道我这个递归结构嵌套了多少个自己:
fn layer(&self) -> usize {
let orin = self.origin.as_ref();
match orin {
Some(itn) => itn.layer() + 1,
None => 1,
}
}
然而这个结构一到 8300 层就栈溢出了.
• 请不要在回答技术问题时复制粘贴 AI 生成的内容
This topic created in 1545 days ago, the information mentioned may be changed or developed.
Supplement 1 · Aug 11, 2022
感谢两位前辈手把手教, 终贴:
-
写成while loop直接有效,benchmark结果花费时间一致
-
我这个函数
ddpp就能改成尾递归了:
fn layer(&self) -> usize {
let orin = self.origin.as_ref();
match orin {
None => 1,
Some(itn) => 1 + itn.layer(),
}
}
芜湖
Supplement 2 · Aug 11, 2022
其实改一个字就可以了, 艹.
fn layer(&self) -> usize {
let orin = self.origin.as_ref();
match orin {
Some(itn) => 1 + itn.layer(),
None => 1,
}
}
 |
1
先查询一下栈空间是多大，然后每个调用帧占多少，除一下就能估测了
|
1 |
2
写成尾递归就好啦
|
 |
MistwaveAug 11, 2022 via iPhone
3
停机问题
|
 |
newmlpAug 11, 2022
4
所有递归都可以用循环替换
|
 |
5
我写 MCU C 代码，会在栈底部写一些特定的 patten 数据，定期检查这些 patten 有没有被修改，从而知道有没有溢出
|
 |
6
```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 } ``` 这样不就完事了？ |
 |
lmshlAug 11, 2022
7
 从汇编结果看，对于你这个函数，O2 级别的优化足以替换成尾递归（迭代）实现了。 你可以手动改成尾递归，让它在任何优化下都能正常工作，或者甩手交给编译器去做 |
 |
8
|
 |
10
尾递归跟迭代没有任何直接联系。
- 可以把尾递归优化成迭代并不意味着常规递归不能被优化成迭代： 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 |
|
11
@andyJado llvm 能把非尾递归优化成尾递归也吓到我了。
当然实际应用中更建议手动写成尾递归形式，以保证 llvm 在任何优化下都可以生成迭代指令 毕竟过于复杂的非尾递归循环，谁也不敢保证编译器是否认得出来 |
Select Language