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

Question

有没有通用的启发式算法、技巧、诀窍或常见的设计范例可以用来将递归算法转换为迭代算法？我知道它是可以完成的，但我想知道在这样做时需要牢记哪些实践经验。

- fbrereto

---

请查看Eric Lippert关于递归的精彩系列文章：http://blogs.msdn.com/ericlippert/archive/tags/Recursion/Rarefied+Heights/default.aspx（从零号部分开始）。 - Joren

我的脑袋刚刚烧了。 - leftclickben

Answer 1

通过使用尾调用和改为传递控制权，可以经常完整保留递归算法的原始结构，但避免使用栈，正如这篇博客文章所建议的那样。（我应该真的想出一个更好的独立示例。）

- Brian

---

当你想要消除递归时，最好避免使用堆栈。 - ldog

博客文章的链接似乎已经不存在了，请更新它。 - pdeva

链接对我来说仍然有效（重定向），但更新后的链接是http://lorgonblog.wordpress.com/2008/06/07/catamorphisms-part-seven/。 - Brian

BDotA：尾调用是指返回语句是对另一个函数的调用。例如，factorial(x) 的递归版本可能在其中某个地方有 return x*factorial(x-1)，这不是尾调用。相反，它可以转换为 return factorial(state*x, x-1)，其中 state 是到目前为止的值。在将所有返回语句转换为调用之后，每个尾调用可以转换为 state = state*x; x = x-1; goto start;。实际上，您不需要使用 goto，因为您可以使用 while 循环。 - Eyal

@Brian：链接和重定向现在已经失效。 - Martin Konecny

Answer 2

我通常在替换递归算法为迭代算法的过程中，使用一种常见技术，即使用堆栈来推送传递给递归函数的参数。

请查看以下文章:

• 使用堆栈替换递归
• 堆栈和递归消除（pdf）

- Christian C. Salvadó

---

如果使用堆栈来消除递归，其实你所做的就是不再使用编程语言的自带堆栈，而是使用自己编写的自定义堆栈，对吗？那这岂不是失去了消除递归的意义？ - ldog

是的，我想问一下海报为什么需要一个通用算法，因为这确实是唯一的一个。 - Claudiu

@ldog: 这难道不违背了初衷吗？不，实际上并没有。程序的栈大小受到严格限制，而用户实现的栈很可能会在自由存储器上分配，那里有更多的空间。我认为，在栈空间不足时将递归转换为迭代是最可能的原因，而这可以解决这个问题。（是的，我意识到这是两年前的帖子，但最近有一个问题与此链接）。 - Benjamin Lindley

@ldog 有时候你需要将一个递归算法转换成不支持递归的语言（比如OpenCL）。 - Jarrett

Answer 3

一种常见的做法是管理一个LIFO堆栈，该堆栈保持一个“待完成任务列表”的运行列表，并在while循环中处理整个过程，直到列表为空为止。采用这种模式，真正递归模型中的递归调用被以下三步代替： - 将当前（部分完成的）任务的“上下文”推入堆栈， - 将新任务（促使递归的任务）推入堆栈 - 并继续（即跳转到）while循环的开头。

在循环头附近，逻辑将最近插入的上下文弹出，并从此开始工作。实际上，这仅仅是将本应保存在嵌套堆栈帧上的信息“移动”到应用程序管理的堆栈容器中。然而，这是一种改进，因为可以在任何地方分配此堆栈容器（递归限制通常与“系统”堆栈中的限制相关）。因此，基本上完成相同的工作，但显式管理“堆栈”允许使用单个循环结构进行操作，而不是使用递归调用。

- mjv

Answer 4

通常情况下，我们可以通过在递归调用中携带一个累加器来代替一般递归，从而实现尾递归。尾递归本质上是迭代的，因为递归调用可以被实现为跳转。例如，标准的阶乘递归定义可以使用尾递归进行改写，将部分结果收集到一个累加器中，并在递归调用时传递下去。

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;

- starblue

---

分支调用的情况怎么办，比如每次调用递归两次，例如树的遍历 - 是否有一种技术可以做到这一点？还是必须使用堆栈方法？ - HaveAGuess

不，这种情况下你必须使用普通递归，因为在第一次调用之后，你必须返回给调用者，然后再进行第二次调用。当然，你可以通过迭代和堆栈来替换普通递归。 - starblue

Answer 5

请查看以下链接，了解有关性能示例的内容：

递归与循环（迭代）：速度和内存比较

和

用迭代替换递归

和

递归与迭代

Q: Is the recursive version usually faster? A: No -- it's usually slower (due to the overhead of maintaining the stack)

  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

we'll need to wait until we've discussed trees to see really good examples...)

- Adriaan Stander

Answer 6

我通常从基本情况开始（每个递归函数都有一个），然后向后工作，并在必要时将结果存储在缓存中（数组或散列表）。

您的递归函数通过解决较小的子问题并使用它们来解决更大的问题实例来解决问题。每个子问题也被进一步分解，直到子问题变得非常小，以至于解决方案是微不足道的（即基本情况）。

这个想法是从基本情况（或基本情况）开始，并使用它来构建更大情况的解决方案，然后使用这些情况来构建更大的情况等等，直到整个问题得到解决。这不需要堆栈，并且可以使用循环完成。

一个简单的例子（用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

- MAK

Answer 7

一个模式是尾递归:

如果在函数返回后没有其他事情可做，除了返回其值，则称函数调用为尾递归。

维基百科。

- Mitch Wheat

---

这不是回答如何将递归问题转换为迭代问题的一般问题（实际上是如何将递归问题转换为尾递归问题）的答案，而且因为脱离上下文的引用不太清楚（函数X在函数Y中处于尾位置，如果函数Y在调用X后除返回该调用的结果外什么也不做；如果它所有递归调用都处于尾位置，则函数是尾递归的）。 - Pete Kirkham