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

Question

我熟悉关于递归的一般意识 - 不要使用它，因为它不是一个好的内存管理实践。然而，这个概念应该适用于所有的编程语言，除非它们能很好地处理递归下的内存管理。

在阅读Educative 的 Rust 课程的文档时，有一个声明：

在 Rust 中递归是可能的，但并不真正鼓励它。相反，Rust 支持称为迭代的东西，也称为循环。

我无法理解为什么会这样？与其他语言相比，Rust 中是否有一些不那么常见的东西，即不建议使用递归或在 Rust 中比其他语言更好地处理迭代？

Answer 1

我无法理解为什么会这样？与其他语言相比，Rust 中是否有一些不那么常见的东西，即不建议使用递归或在 Rust 中比其他语言更好地处理迭代？

大多数语言都非常“喜欢”迭代而不是递归，他们只是不想那么明确地拼写出来。例如，Python对递归深度有解释器级别的限制，默认值为 1000。

这可能是明确指出了锈，因为它的根源在于函数式语言它们基本上是唯一的有利于递归部分：许多结构都是按MLS和Haskell和最初的灵感来自编译为OCaml中，我不认为甚至有一个构造迭代（也称为任何类型的for或while循环）。

至于为什么一种语言会支持迭代，而不支持递归：如果没有尾调用消除（TCE），递归会导致堆栈空间的消耗，可能是无限的。

如果语言使用 C 堆栈并且除非它也设置了自己的递归限制，否则它无法轻松知道堆栈的深度：Linux 上的默认值可以高达 8MB（实际上是 glibc），低至 64k对于 OpenBSD（至少在 OpenBSD 4 的时代），查询这些信息的方法很少，也没有真正的方法来彻底检查它（加上检查不会是免费的）。更成问题的是，堆栈溢出充其量只会导致段错误（程序硬崩溃），更糟糕的是会导致内存不安全，因此这是您真正想要避免的。

即使没有那个——再次假设你没有 TCE——一个以递归方式实现的无界循环（例如一个事件循环）将消耗无限量的内存，因为每个递归调用都会保留一个永远不会作为函数回收的堆栈帧永远不会回来。

无限迭代循环可能会消耗 100% 的 CPU（如果你没有做任何等待 IO 事件或锁的事情），但不会吃掉你所有的内存，除非你特别明确地积累数据（例如推送东西）成向量）。

如果您确实有 TCE，那么从技术上讲，您根本不需要迭代，而且实际上很多语言都不会为此烦恼。据我所知，OCaml 和 Erlang（这根本不是一个详尽的列表，但我有理由肯定这两个）没有任何类型的循环构造，只要您的递归调用处于尾部位置，它就会被优化离开。

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

最后，在答案中我专门讨论了尾调用消除(TCE)。你可能听说过尾调用优化(TCO)，Rust 之所以有它，是因为它的后端是具有 TCO 的 LLVM。

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