recursion - 从递归到迭代的方法

Question

在多年的编程生涯中，我经常使用递归来解决简单的问题，但我完全意识到，有时由于内存/速度问题，您需要迭代。

所以，在很久以前的某个时候，我尝试寻找是否存在任何“模式”或教科书方式将常见的递归方法转换为迭代，但一无所获。或者至少我记得没有任何帮助。

• 有一般规则吗？
• 有“模式”吗？

Answer 1

通常，我通过将通常传递给递归函数的参数推送到堆栈上，用迭代算法替换递归算法。事实上，您正在用您自己的程序堆栈替换程序堆栈。

var stack = [];
stack.push(firstObject);

// while not empty
while (stack.length) {

    // Pop off end of stack.
    obj = stack.pop();

    // Do stuff.
    // Push other objects on the stack as needed.
    ...

}

注意:如果你有多个递归调用，并且你想保留调用的顺序，你必须以相反的顺序将它们添加到堆栈中:

foo(first);
foo(second);

必须替换为

stack.push(second);
stack.push(first);

编辑:文章Stacks and Recursion Elimination (或 Article Backup link )详细介绍此主题。