在我多年的编程生涯中，我经常使用递归来解决简单的问题，但我完全意识到，有时由于内存/速度问题，您需要迭代。
所以，在很久以前的某个时候，我去尝试寻找是否存在任何“模式”或教科书上的方法来将常见的递归方法转换为迭代，但一无所获。至少我想不起有什么帮助。
有一般的规则吗? 有“模式”吗?
当前回答
这个链接提供了一些解释，并提出了保持“位置”的想法，以便能够在几个递归调用之间到达确切的位置:
但是，所有这些示例都描述了递归调用进行固定次数的场景。当你遇到以下情况时，事情就变得棘手了:
function rec(...) {
for/while loop {
var x = rec(...)
// make a side effect involving return value x
}
}
其他回答
即使使用堆栈也不能将递归算法转换为迭代算法。普通的递归是基于函数的递归，如果我们使用堆栈，那么它就变成了基于堆栈的递归。但它仍然是递归。
对于递归算法，空间复杂度为O(N)，时间复杂度为O(N)。 对于迭代算法，空间复杂度为O(1)，时间复杂度为O(N)。
但是如果我们使用堆栈的话复杂度还是一样的。我认为只有尾递归可以转化为迭代。
通常，通过将通常传递给递归函数的参数推入堆栈，我将递归算法替换为迭代算法。事实上，您正在用自己的程序堆栈替换程序堆栈。
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);
编辑:文章堆栈和递归消除(或文章备份链接)详细介绍了这个主题。
实际上，最常见的方法是保留自己的堆栈。下面是一个C语言的递归快速排序函数:
void quicksort(int* array, int left, int right)
{
if(left >= right)
return;
int index = partition(array, left, right);
quicksort(array, left, index - 1);
quicksort(array, index + 1, right);
}
以下是我们如何通过保持自己的堆栈来实现迭代:
void quicksort(int *array, int left, int right)
{
int stack[1024];
int i=0;
stack[i++] = left;
stack[i++] = right;
while (i > 0)
{
right = stack[--i];
left = stack[--i];
if (left >= right)
continue;
int index = partition(array, left, right);
stack[i++] = left;
stack[i++] = index - 1;
stack[i++] = index + 1;
stack[i++] = right;
}
}
显然，这个例子没有检查堆栈边界……实际上，你可以根据最坏的情况来确定堆栈的大小。但你懂的。
只是消磨时间……递归函数
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
foo(node->left);
foo(node->right);
}
可转换为
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
stack.push(node->right);
stack.push(node->left);
while(!stack.empty()) {
node1 = stack.pop();
if(node1 == NULL)
continue;
// Do something with node1...
stack.push(node1->right);
stack.push(node1->left);
}
}
有一种将递归遍历转换为迭代器的通用方法，即使用连接多个迭代器提供者的惰性迭代器(返回迭代器的lambda表达式)。请参阅我的将递归遍历转换为迭代器。
