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

Question

是否有任何通用的启发式,提示,技巧或常用设计范例可用于将递归算法转换为迭代算法？我知道可以做到,我想知道在这样做的时候是否有值得牢记的做法.

Answer 1

你可以经常保持完全递归算法的原始结构,但要避免堆栈,采用尾调用并改变延续传递,所建议这个博客条目.(我应该做一个更好的独立示例.)

Answer 2

我在使用迭代替换递归算法的过程中使用的常用技术通常是使用堆栈,推送传递给递归函数的参数.

检查以下文章:

• 用堆栈替换递归
• 堆栈和递归消除(pdf)

Answer 3

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

实际上,这仅仅"移动"了本来保存在"系统"堆栈上的嵌套堆栈帧中的信息到应用程序管理的堆栈容器.然而,这是一种改进,因为这个堆栈容器可以分配到任何地方(递归限制通常与"系统"堆栈中的限制相关联).因此,基本上完成相同的工作,但是"堆栈"的显式管理允许这发生在单个循环结构而不是递归调用中.

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;