是否有任何通用的启发式方法、提示、技巧或通用设计范例可用于将递归算法转换为迭代算法？我知道可以做到，我想知道这样做时是否有值得牢记的做法。
问问题
30206 次
7 回答
30
您通常可以完全保留递归算法的原始结构，但通过使用尾调用并更改为continuation-passing来避免堆栈，正如此博客条目所建议的那样。（我真的应该编写一个更好的独立示例。）
于 2009-10-11T07:40:00.790 回答
8
一种常见的做法是管理一个 LIFO 堆栈，该堆栈保留一个运行列表，其中包含“还有待完成的工作”，并在 while 循环中处理整个过程，该循环一直持续到列表为空。
使用这种模式，真正递归模型中的递归调用被替换为
- 将当前（部分完成）任务的“上下文”推送到堆栈上，
- 将新任务（提示递归的任务）推送到堆栈
- 并“继续”（即跳转到开头）while 循环。在循环头部附近，逻辑弹出最近插入的上下文，并在此基础上开始工作。
实际上，这只是将原本保存在“系统”堆栈上的嵌套堆栈帧中的信息“移动”到应用程序管理的堆栈容器。然而，这是一个改进，因为这个堆栈容器可以分配到任何地方（递归限制通常与“系统”堆栈中的限制相关联）。因此基本上完成了相同的工作，但是“堆栈”的显式管理允许这发生在单个循环构造中，而不是递归调用。
于 2009-10-11T06:01:47.057 回答
7
通常，一般递归可以用尾递归代替，方法是在累加器中收集部分结果并通过递归调用将其传递下去。尾递归本质上是迭代的，递归调用可以实现为跳转。
例如，阶乘的标准通用递归定义
factorial(n) = if n = 0 then 1 else n * factorial(n - 1)
可以替换为
factorial(n) = f_iter(n, 1)
和
f_iter(n, a) = if n = 0 then a else f_iter(n - 1, n * a)
这是尾递归。它与
a = 1;
while (n != 0) {
a = n * a;
n = n - 1;
}
return a;
于 2009-10-11T08:30:56.303 回答
4
查看这些链接以获取性能示例
和
和
问：递归版本通常更快吗？A：不——它通常更慢（由于维护堆栈的开销）
Q: Does the recursive version usually use less memory? A: No -- it usually uses more memory (for the stack). Q: Then why use recursion?? A: Sometimes it is much simpler to write the recursive version (but我们需要等到我们讨论了树才能看到真正好的例子......）
于 2009-10-11T05:44:22.473 回答
4
我通常从基本情况（每个递归函数都有一个）开始，然后向后工作，如有必要，将结果存储在缓存（数组或哈希表）中。
您的递归函数通过解决较小的子问题并使用它们来解决问题的较大实例来解决问题。每个子问题也被进一步分解，以此类推，直到子问题非常小以至于解决方案是微不足道的（即基本情况）。
这个想法是从基本案例（或基本案例）开始，并使用它为更大的案例构建解决方案，然后使用这些案例来构建更大的案例等等，直到整个问题得到解决。这不需要堆栈，并且可以通过循环来完成。
一个简单的例子（在 Python 中）：
#recursive version
def fib(n):
if n==0 or n==1:
return n
else:
return fib(n-1)+fib(n-2)
#iterative version
def fib2(n):
if n==0 or n==1:
return n
prev1,prev2=0,1 # start from the base case
for i in xrange(n):
cur=prev1+prev2 #build the solution for the next case using the previous solutions
prev1,prev2=cur,prev1
return cur
于 2009-10-12T19:00:41.300 回答