为什么不建议在Rust中使用递归？

Question

为什么不建议在Rust中使用递归？

recursionrust

27

我了解关于递归的一般认知 - 不要使用它，因为它不是良好的内存管理实践。但是，除非编程语言在递归下处理内存管理真的很好，否则这个概念应该被应用到所有的编程语言中。

在浏览Educative Rust课程的文档时，有一个声明:

Rust可以进行递归，但并不是真正鼓励使用。相反，Rust更喜欢一种叫做迭代的东西，也就是循环。

我无法理解这是为什么？与其他语言相比，Rust是否存在一些不太常见的东西，导致不建议使用递归或者迭代在Rust中比其他语言中处理得更好？

- Aviral Srivastava

5

这段内容不是很针对Rust，但递归会在堆栈上构建，可能导致堆栈溢出，而迭代解决方案则不会。你可以防范无法分配内存，但不能防范栈内存不足。我还认为尾部优化在Rust中未实现，但已列入计划（或可能已被实现）。 - Ted Klein Bergman

1

一个小的原因：https://dev59.com/elkS5IYBdhLWcg3wdmcx#39840726 - Dee

1

在所有编程语言中，迭代是否比递归更受青睐（尽可能）？这并不令人惊讶。 - user202729

2

@user202729 使用TCE（不要与TCO混淆）的编程语言对递归非常满意。它们甚至可能没有命令式迭代（例如Erlang）。 - Masklinn

@Masklinn …啊，那就是在C家族语言中了。 - user202729

1

另外还有几点需要考虑。递归可能比需要堆分配的迭代替代方案更快。构建一个迭代函数（即循环）使得转换为 Rust 迭代器更容易（即将所有状态存储在结构体中并实现 Iterator），这反过来又使得支持异步执行更容易（调用迭代器以推进函数）。在 Rust 中，迭代也可以帮助避免显式定义生命周期，如果您正在传递和返回引用，则可能会引入生命周期。 - optevo

1个回答

网页内容由stack overflow 提供, 点击上面的

可以查看英文原文，
原文链接

- Masklinn · Accepted Answer

我无法理解为什么会这样？在Rust中是否有一些与其他语言不同的不常见特性，使得递归不被建议，或者在Rust中迭代比其他语言更好处理？

大多数语言非常“喜欢”迭代而不是递归，只是它们没有明确地表述出来。例如，Python 在解释器级别上限制递归深度，默认值很低，只有1000。

这可能会在Rust中明确说明，因为它的起源部分在于函数式语言，这些语言基本上是唯一支持递归的语言：许多构造受到ML和Haskell的启发，最初的编译器是OCaml编写的，我认为甚至没有迭代结构（也就是任何类型的for或while循环）。

关于为什么语言会偏向迭代，而不赞成递归：没有尾调用消除（TCE），递归将导致堆栈空间的消耗，可能是无界的。

如果语言使用C堆栈，并且除非它还设置自己的递归限制，否则它没有办法轻松知道堆栈可以有多深：默认值在Linux上可以高达8MB（实际上是glibc），而在OpenBSD 4的时代至少为64k，查询此信息的方法非常少，也没有真正干净的检查方法（加上检查也不会免费）。更为问题的是，堆栈溢出最好会导致段错误（硬崩溃程序），在更糟糕的情况下会导致内存不安全，因此这是您确实想避免的事情。

即使没有那个问题-并再次假设您没有TCE-以递归方式实现的无界循环（例如事件循环）将消耗无限量的内存，因为每个递归调用都会保留一个stack frame，该函数永远不会返回。

一个无限迭代的循环可能会烧掉你100%的CPU（如果你没有做任何等待IO事件或锁定的操作），但除非你明确地累积数据（例如将东西推入向量中），否则不会占用所有内存。

如果您确实拥有尾递归消除（TCE），那么从技术上讲，您根本不需要迭代，实际上有许多语言不会涉及到它。据我所知，OCaml和Erlang（这并不是详尽无遗的列表，但我相当确定这两个）没有任何循环结构，只要你的递归调用在尾部位置，它就会被优化掉。

后面那一点使它稍微复杂一些，并且容易出错：为了使TCE起作用，调用必须处于尾部位置，也就是你做的最后一件事情：foo()是一个尾递归调用，但1+foo()不是，加法在尾部位置而不是调用。这意味着很容易错误地使函数非尾递归，并且通常需要将循环作为辅助累加器函数来解决问题（例如，在上面的例子中，您可以调用foo2(1)而不是1 + foo()，它会在内部执行增量操作，类似于这样）。语言设计人员和实现者需要指定和实现TCE，这需要一些努力，可能会限制您的选择等等...

最后，在回答中，我特别谈到了尾调用消除（TCE）。你可能听说过尾调用优化（TCO），Rust具有此功能，因为其后端是LLVM，具有TCO。

TCO的问题在于，优化意味着启发式和一定的机会性：编译器可能会根据调用类型、函数大小、参数数量（和大小）、控制流等来优化递归，也可能不会这样做，并且优化甚至可能没有在所有后端上实现。这意味着如果你要使语言在没有迭代结构的情况下工作，TCO不能成为语言语义的基础，你需要在出现时可靠地删除尾调用。因此，你需要尾调用消除而不是仅仅是优化。