在我多年的编程生涯中，我经常使用递归来解决简单的问题，但我完全意识到，有时由于内存/速度问题，您需要迭代。
所以，在很久以前的某个时候，我去尝试寻找是否存在任何“模式”或教科书上的方法来将常见的递归方法转换为迭代，但一无所获。至少我想不起有什么帮助。
有一般的规则吗? 有“模式”吗?
当前回答
通常，通过将通常传递给递归函数的参数推入堆栈，我将递归算法替换为迭代算法。事实上，您正在用自己的程序堆栈替换程序堆栈。
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);
编辑:文章堆栈和递归消除(或文章备份链接)详细介绍了这个主题。
其他回答
通常，通过将通常传递给递归函数的参数推入堆栈，我将递归算法替换为迭代算法。事实上，您正在用自己的程序堆栈替换程序堆栈。
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;
}
}
显然，这个例子没有检查堆栈边界……实际上，你可以根据最坏的情况来确定堆栈的大小。但你懂的。
一个系统如何接受任何递归函数并使用堆栈执行它的粗略描述:
这是为了在没有细节的情况下展示想法。考虑这个函数，它将打印出图的节点:
function show(node)
0. if isleaf(node):
1. print node.name
2. else:
3. show(node.left)
4. show(node)
5. show(node.right)
例如图表: A - B > C - > show(A)将打印B, A, C
函数调用意味着保存本地状态和延续点，以便返回，然后跳转到要调用的函数。
例如，假设show(A)开始运行。函数调用在第3行。显示(B)的意思 -将项目添加到堆栈，意思是“你需要在第2行继续使用本地变量状态node=A” —到第0行，节点为B。
为了执行代码，系统运行指令。当遇到函数调用时，系统将需要的信息推回到原来的位置，运行函数代码，当函数完成时，弹出关于需要继续执行的位置的信息。
似乎没有人指出递归函数在主体中调用自己超过一次的位置，并处理返回递归中的特定点(即不是原始递归)。据说每一个递归都可以转化为迭代，所以这似乎是可能的。
我刚刚想出了一个如何做到这一点的c#示例。假设您有以下递归函数，它的作用类似于poststorder遍历，AbcTreeNode是一个带有指针a、b、c的3元树。
public static void AbcRecursiveTraversal(this AbcTreeNode x, List<int> list) {
if (x != null) {
AbcRecursiveTraversal(x.a, list);
AbcRecursiveTraversal(x.b, list);
AbcRecursiveTraversal(x.c, list);
list.Add(x.key);//finally visit root
}
}
迭代解:
int? address = null;
AbcTreeNode x = null;
x = root;
address = A;
stack.Push(x);
stack.Push(null)
while (stack.Count > 0) {
bool @return = x == null;
if (@return == false) {
switch (address) {
case A://
stack.Push(x);
stack.Push(B);
x = x.a;
address = A;
break;
case B:
stack.Push(x);
stack.Push(C);
x = x.b;
address = A;
break;
case C:
stack.Push(x);
stack.Push(null);
x = x.c;
address = A;
break;
case null:
list_iterative.Add(x.key);
@return = true;
break;
}
}
if (@return == true) {
address = (int?)stack.Pop();
x = (AbcTreeNode)stack.Pop();
}
}
只是消磨时间……递归函数
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);
}
}
