每个递归过程都可以转化为迭代过程吗？

Question

我正在阅读书籍《计算机程序的构造与解释》，其中介绍了递归过程和递归程序之间的区别，以及迭代过程和迭代程序之间的类似区别。因此，递归程序仍可以生成迭代过程。

我的问题是：如果给定一个生成递归过程的程序，你能否总是编写另一个程序来实现相同的结果，但生成迭代过程？

我尝试解决的具体问题是编写一个遍历二叉搜索树的中序遍历程序，但生成迭代过程。我知道您可以使用堆栈来获得此问题的迭代程序。但是，这仍然会生成递归过程（如果我错了，请纠正我）。

谢谢， Abhinav。

- abhinav

Answer 1

有些任务无法通过线性迭代过程来解决（例如树形递归，无法转换为尾递归）。您必须使用平台内置的堆栈，或者在语言中重新创建它（通常是一种效率较低且更难看的解决方案）。

因此，如果您将“递归”定义为“使用堆栈存储同一代码的不同调用”，那么有时确实需要使用递归。

如果您将“递归”定义为“我的语言中的函数最终调用自身”，那么您可以通过自己重新实现递归来避免显式递归，如上所述。只有当您的语言不提供递归过程，或者没有足够的堆栈空间，或者存在类似的限制时，才会有用。（例如，早期的Fortran没有递归过程。当然，它们也没有模拟它们需要的动态数据结构！个人而言，我从未遇到过实际的例子，其中实现伪递归是正确的解决方案。）

- Kilian Foth

---

谢谢您的解释。我认为您想说的是并非所有树递归都可以转换为尾递归 :) SICP演示了如何使用尾递归获得计算斐波那契数列的迭代过程。 - abhinav

可以，但这仅仅因为天真方法的左右分支是自相似的。这使您可以使用线性递推 - 实际上，它允许O（1）解决方案！换句话说，原始定义并不是首先解决问题的正确方法。不幸的是，几乎所有介绍性文本都将斐波那契数列作为树递归的示例，尽管该概念实际上是一个非常糟糕的例子。 - Kilian Foth

@KilianFoth为什么你说树递归不能转化为迭代（尾递归）过程？这只是一个正确排序节点的顺序问题。通过传递样式可以轻松解决这个问题 - https://dev59.com/qXfZa4cB1Zd3GeqPQ2Fw - Mulan

Answer 2

阅读这篇以前的SO帖子:

用于将递归算法转换为迭代算法的设计模式

那里有很多好的答案，可能会对你有所帮助。

- Doc Brown

Answer 3

任何尾递归过程都可以转化为迭代过程。但并非所有递归过程都可以转换为迭代过程。

- leppie

---

你能解释一下什么是尾递归过程以及其他递归过程的类别吗？或者给个指针吗？谢谢。 - Serge Wautier

谢谢您的澄清。您能提供一个参考资料，让我了解为什么所有递归过程都不能转化为迭代过程吗？ - abhinav

@abhinav：深度优先树遍历是一个难以或不可能迭代编写的例子。 - leppie