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

您通常可以完全保留递归算法的原始结构，但通过使用尾部调用并将其更改为延续传递（如本博客条目所建议的那样），可以避免使用堆栈。 （我应该制作一个更好的独立示例。）

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

检查以下文章：

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

一种常见的做法是管理一个LIFO堆栈，该堆栈保留正在运行的列表“尚待完成”，并在while循环中处理整个过程，直到该列表为空。
通过这种模式，在真正的递归模型中将被递归调用替换为
-将当前（部分完成的）任务的“上下文”推入堆栈，
-将新任务（提示递归的任务）压入堆栈
-并在while循环中“继续”（即跳转到开头）。在循环的开头附近，逻辑弹出最近插入的上下文，并在此基础上开始工作。

有效地，这仅仅是将本应保留在“系统”堆栈上的嵌套堆栈框架中的信息“移动”到应用程序管理的堆栈容器。 但是，这是一个改进，因为此堆栈容器可以分配到任何位置（递归限制通常与“系统”堆栈中的限制联系在一起）。 因此，基本上完成了相同的工作，但是对“堆栈”的显式管理使之可以在单个循环结构中进行，而不必进行递归调用。

通常，通过在累加器中收集部分结果并将其与递归调用一起传递，可以将尾递归替换为一般递归。 尾递归本质上是迭代的，递归调用可以实现为跳转。

例如，阶乘的标准通用递归定义

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;

查看这些链接以获取性能示例

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

和

用迭代替换递归

和

递归与迭代

问：通常是递归版本吗 快点？ 答：不会-通常会比较慢（由于维护的开销 堆栈）

  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

我们需要等到 讨论过的树木，看真的很好 例子...）

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

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

这个想法是从一个或多个基本案例开始，并用它来为较大的案例构建解决方案，然后再使用这些案例来构建较大的案例，依此类推，直到解决了整个问题。 这不需要堆栈，可以通过循环来完成。

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

一种模式是尾递归：

一个函数调用被称为tail 递归，如果无事可做 函数返回后除外 返回其值。

维基。