每个递归算法都可以创建一个等价的非递归版本吗？

Question

递归很有趣。然而，在安全关键应用中，它被视为一件危险的事情（因为可能会导致堆栈溢出？）。

想象一下，如果您需要处理您喜欢的语言的子集，但不允许使用递归——那对您来说是否是一场灾难？

正式问题：对于每个递归函数，都可以创建一个完全等效的非递归函数吗？这是真的吗？还是有关于此的定理或其他东西？

- Vladimir Keleshev

---

你查过 Stack Overflow 吗？https://dev59.com/QnI95IYBdhLWcg3w7CjL - Marnix

递归并不好玩...它让我的大脑感到疼痛。 - Caspar Kleijne

递归很棒。相较于循环，它在程序验证方面更简单，并且可以产生漂亮的代码。 - Fred Foo

递归模拟真的很费脑子。有些算法用递归表达更清晰。 - user180326

Answer 1

想象一下，你的程序由有限数量的CPU执行（假设你目前只有1个），并执行一系列指令。那么CPU如何处理递归呢? 它不能创建一个解决稍微简单问题的新实例，所以它使用堆栈来跟踪自己所在的位置。因此，对于任何你可以用任何编程语言递归表达的算法，你也可以手动“展开”递归，就像CPU使用堆栈一样。（请注意，对于许多算法，特别是只有一个递归调用的算法，通常有更简单的方法来消除递归，比如简单的迭代。）

- Daniel Gallagher

---

还要注意，对于许多其他算法（如树遍历），除递归之外的唯一可行方法是手动管理堆栈。同时还要注意，这并不是一件有趣的事情，因此在这些情况下最好坚持使用递归。 - user395760

Answer 2

是的，每个这样的函数都可以被重写为一个非递归函数。我不确定是否有一种正式的方法来做到这一点，但它在文献中被称为“递归展开”或“递归展开”。

在大多数情况下，应避免使用递归。特别是在所提到的那种系统中，例如MISRA-C禁止使用递归。

有一些罕见的情况下，递归很方便并使代码更有效率，例如一些二叉树的实现等。

但递归的主要目的是将其教给困惑的学生，以便当他们变得经验丰富时，他们可以将其教给困惑的学生，以便-...:)

- Lundin

---

规范和正式的方法是使用CPS转换。这对人类来说本质上是容易出错的。任何理智的算法语言都应该通过实现（例如编译器）支持它或一些等效的方法。在源代码中禁止递归调用的事实在这个意义上真的很愚蠢，因为它促进了残疾的语言设计，这种设计会鼓励错误。 - FrankHB

我知道你很久以前写了这个，但那只是递归的一个相对有限的视角。在一些编程语言中，尾递归不仅仅是潜在的优化，而且可以安全地执行递归操作。 - 2-bits

没错。那些因为太慢而臭名昭著的语言，无论你如何努力都注定会产生一条臃肿的字节码河流，垃圾回收员漫不经心地划着船，慢慢地捞拾着垃圾。 - Lundin

比Scheme更多的语言允许使用这个特性。Haskell，Kotlin，Scala，F＃甚至C＃（在适当的情况下）都可以以一种不会导致栈溢出的方式处理尾调用，有些语言如Haskell可以非常快。任何语言都应该能够做到这一点，但对于某些语言而言，这是一种要求而不是优化。GCC为C执行此操作（启用优化），我相信您不会说它很慢。递归确实很有用。 "适用于嵌入式系统"是许多程序员永远不必使用的标准，在我看来不是拒绝其使用的好理由。 - 2-bits

Answer 3

递归不是免费的

它需要相当数量的内存空间（通常在堆栈上）
和CPU时间（通过调用、重建堆栈框架等）。
在紧密循环中，这使得递归算法比其非递归等效算法慢。

如果速度和堆栈限制不是问题，那么请保留递归，但如果您在紧密循环中使用递归（这经常是情况），
通过消除递归，您可以获得很多优化选项。

因为：也许：
1. 您不需要保存所有这些寄存器/变量
2. 您不必跳回到从哪里来的确切位置。
3. 您不需要为每个递归调用那个清理代码
4. 您可以展开一些循环
5. 您可以在那个非递归程序上使用inline指令。

我对递归的主要问题是它最常用于的数据结构：树。

树需要指针，而指针需要随机内存访问（它们跳来跳去），这对缓存使用不利，因为顺序访问比随机访问快得多。
如果您用2D数组替换二叉树，则会浪费50％的空间（除非您在数组中倒置另一棵树），但是您可以获得许多叶子节点的顺序访问选项，并且无需使用指针，从而节省空间。

Example of a binary tree stored in an array
+-----------------+
|0eeeeeeeeeeeeeeee| //no pointers needed, parent/child, is y dimension,
|11       dddddddd| //sibbling is x dimension of the array.
|2222         cccc|  //The 123 tree is stored root up.
|33333333       bb|  //Notice how the abc-tree is stored upside down 
|4444444444444444a|  //The wasted space in the middle, is offset by the fact 
+-----------------+  //that you do not need up, down, and sibbling pointers.

- Johan

Answer 4

通常使用递归是因为没有简单的方法来知道需要迭代多少次才能解决问题。

如果你觉得必要，用简单的循环替换递归函数可能需要大量额外的工作，但通常是可行的。

不过，如果你的递归函数有一个合适的基本情况，那么堆栈溢出的风险就很小了。

- jeffszusz