这是一个创建于 820 天前的主题，其中的信息可能已经有所发展或是发生改变。
单纯的想知道我这个递归结构嵌套了多少个自己:
fn layer(&self) -> usize {
let orin = self.origin.as_ref();
match orin {
Some(itn) => itn.layer() + 1,
None => 1,
}
}
然而这个结构一到 8300 层就栈溢出了.
第 1 条附言 · 2022-08-11 18:24:47 +08:00
感谢两位前辈手把手教, 终贴:
-
写成while loop直接有效,benchmark结果花费时间一致
-
我这个函数
ddpp就能改成尾递归了:
fn layer(&self) -> usize {
let orin = self.origin.as_ref();
match orin {
None => 1,
Some(itn) => 1 + itn.layer(),
}
}
芜湖
第 2 条附言 · 2022-08-11 18:27:29 +08:00
其实改一个字就可以了, 艹.
fn layer(&self) -> usize {
let orin = self.origin.as_ref();
match orin {
Some(itn) => 1 + itn.layer(),
None => 1,
}
}
 |
1
kenvix 2022-08-11 12:04:40 +08:00  1
先查询一下栈空间是多大，然后每个调用帧占多少，除一下就能估测了
|
 |
2
IMXT 2022-08-11 12:06:45 +08:00 via iPhone 1
写成尾递归就好啦
|
 |
3
Mistwave 2022-08-11 12:55:51 +08:00 via iPhone
停机问题
|
 |
4
newmlp 2022-08-11 14:12:17 +08:00
所有递归都可以用循环替换
|
 |
5
duke807 2022-08-11 14:29:30 +08:00 via Android 1
我写 MCU C 代码，会在栈底部写一些特定的 patten 数据，定期检查这些 patten 有没有被修改，从而知道有没有溢出
|
 |
6
PTLin 2022-08-11 15:11:45 +08:00 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 } ``` 这样不就完事了？ |
 |
7
lmshl 2022-08-11 16:08:24 +08:00
 从汇编结果看，对于你这个函数，O2 级别的优化足以替换成尾递归（迭代）实现了。 你可以手动改成尾递归，让它在任何优化下都能正常工作，或者甩手交给编译器去做 |
 |
8
andyJado OP |
|
9
PTLin 2022-08-11 18:48:39 +08:00
@andyJado 你当这是 haskell 吗？还避免 if while ，你在 rust 里计算递归结构长度就算有优化也不能考虑用递归算啊
|
 |
10
lxdlam 2022-08-11 18:55:25 +08:00 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 |
Select Language