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

Question

我正在阅读《计算机程序的结构和解释》一书，其中讲述了递归过程和递归过程之间的区别，以及迭代过程和迭代过程之间的区别。因此，递归过程仍然可以生成迭代过程。

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

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

谢谢，
阿比纳夫。

Answer 1

有些任务确实不可能用线性迭代过程来解决（例如树递归，它不可能转换为尾递归）。您要么必须使用平台内置的堆栈，要么自己在语言中重新创建它（通常是效率低得多且丑陋得多的解决方案）。因此，如果您将“递归”定义为“使用堆栈存储同一代码的不同调用”，那么是的，有时绝对需要递归。

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

Answer 2

阅读这篇以前的 SO 帖子：

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

那里有很多很好的答案，可以进一步帮助你。

Answer 3

任何尾递归过程都可以转换为迭代过程。

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