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

Question

我熟悉关于递归的一般意识 - 不要使用它，因为它不是一个好的内存管理实践。然而，这个概念应该适用于所有的编程语言，除非它们能很好地处理递归下的内存管理。
在通过 documentation from Educative's Rust course 时，有一个声明:

Recursion is possible in Rust, but it’s not really encouraged. Instead, Rust favors something called iteration, also known as looping.

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

Answer 1

I am unable to grasp why is this the case? Is there something not-so-common in Rust as compared to other languages that recursion is not suggested or iteration is handled better in Rust than in other languages?

大多数语言都非常“喜欢”迭代而不是递归，他们只是不想那么明确地拼写出来。例如，Python has an interpreter-level limit on recursion depth一个微不足道的默认值 1000。
Rust 可能会明确指出这一点，因为它的起源部分在于函数式语言，这些语言基本上是唯一支持递归的语言:许多构造都受到 MLs 和 Haskell 的启发，并且最初的编译器是在 OCaml 中，我认为它甚至没有用于迭代的构造(也就是任何类型的 for 或 while 循环)。

至于为什么一种语言会支持迭代，而不支持递归:如果没有尾调用消除(TCE)，递归会导致堆栈空间的消耗，可能是无限的。
如果语言使用 C 堆栈，除非它也设置了自己的递归限制，否则无法轻松知道堆栈的深度:Linux 上的默认值可以高达 8MB(实际上是 glibc)，低至 64k对于 OpenBSD(至少在 OpenBSD 4 的时代)，查询这些信息的方法很少，也没有真正的方法来彻底检查它(加上检查不会是免费的)。更成问题的是，堆栈溢出充其量只会导致段错误(使程序崩溃)，更糟糕的是会导致内存不安全，因此这是您真正想要避免的。
即使没有那个——再次假设你没有 TCE——一个以递归方式实现的无界循环(例如一个事件循环)将消耗无限量的内存，因为每个递归调用都会保留一个 stack frame它永远不会被回收，因为函数永远不会返回。
无限迭代循环可能会消耗 100% 的 CPU(如果您没有做任何等待 IO 事件或锁的事情)，但不会吃掉所有内存，除非您特别明确地积累数据(例如推送内容)成向量)。

如果您确实有 TCE，那么从技术上讲，您根本不需要迭代，而且实际上很多语言都不会为此烦恼。据我所知，OCaml 和 Erlang(这根本不是一个详尽的列表，但我有理由肯定这两个)没有任何类型的循环构造，只要您的递归调用处于尾部位置，它就会被优化离开。
后一点使它稍微复杂一些，并且容易出错:要使 TCE 工作，调用必须处于尾部位置，这意味着您要做的最后一件事: foo()是尾调用，但是 1 + foo()不是，加法是在尾部位置而不是调用。这意味着很容易错误地使函数成为非尾递归函数，并且您经常需要将循环具体化为基于辅助累加器的函数来解决该问题(例如，在上述情况下，您会调用 1 + foo() 而不是 foo2(1) 并且它会在内部执行增量，类似这样)。语言设计者和实现者需要指定和实现 TCE，这需要一些努力，可以限制您的选择等...

最后，在答案中我专门讨论了尾调用消除 (TCE)。您可能听说过尾调用优化 (TCO)，Rust 之所以如此是因为 its backend is LLVM which has TCO .
TC的问题 Ø 优化意味着启发式和机会元素:编译器可能会或可能不会根据调用类型、函数大小、参数的数量(和大小)、控制流等优化递归，并且优化甚至可能不会在所有后端实现。这意味着 TCO 不能成为语言语义的基础 如果你想让你的语言在没有迭代结构的情况下工作，你需要在尾调用出现时可靠地删除它们。因此，您需要消除尾调用，而不仅仅是优化。