https://stackoverflow.com/questions/159590
-
03-07-2019 - |
italiano
english
français
española
中国
日本の
العربية
Deutsch
한국어
Português
Russian题
在多年的编程生涯中，我经常使用递归来解决简单的问题，但我完全意识到，有时由于内存/速度问题，您需要迭代。
因此，在很久以前的某个时候，我尝试寻找是否存在任何“模式”或教科书方式将常见的递归方法转换为迭代，但一无所获。或者至少我记得没有任何帮助。
- 有一般规则吗？
- 有“模式”吗？
解决方案
通常，我通过将通常传递给递归函数的参数推送到堆栈上，用迭代算法替换递归算法。事实上，您正在用您自己的程序堆栈替换程序堆栈。
Stack<Object> stack;
stack.push(first_object);
while( !stack.isEmpty() ) {
// Do something
my_object = stack.pop();
// Push other objects on the stack.
}
笔记：如果内部有多个递归调用并且您想保留调用的顺序，则必须以相反的顺序将它们添加到堆栈中：
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;
}
}
显然，这个例子没有检查堆栈边界......实际上，您可以根据给定左值和右值的最坏情况调整堆栈大小。但你明白了。
似乎没有人解决递归函数在函数体内多次调用自身的问题，并处理返回递归中的特定点（即。不是原始递归）。据说 每个递归都可以变成迭代, ，所以看来这应该是可能的。
我刚刚想出了一个 C# 示例来说明如何执行此操作。假设您有以下递归函数，其作用类似于后序遍历，并且 AbcTreeNode 是带有指针 a、b、c 的三叉树。
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();
}
}
努力进行递归调用 尾递归 （递归，其中最后一条语句是递归调用）。一旦掌握了这一点，将其转换为迭代通常非常容易。
嗯，一般来说，只需使用存储变量即可将递归模仿为迭代。请注意，递归和迭代通常是等效的；一种几乎总是可以转换为另一种。尾递归函数很容易转换为迭代函数。只需将累加器变量设置为局部变量，然后迭代而不是递归即可。这是 C++ 中的一个示例（如果不使用默认参数，则为 C）：
// tail-recursive
int factorial (int n, int acc = 1)
{
if (n == 1)
return acc;
else
return factorial(n - 1, acc * n);
}
// iterative
int factorial (int n)
{
int acc = 1;
for (; n > 1; --n)
acc *= n;
return acc;
}
了解我，我可能在代码中犯了一个错误，但想法是存在的。
即使使用堆栈也不会将递归算法转换为迭代算法。普通递归是基于函数的递归，如果我们使用堆栈，那么它就变成基于堆栈的递归。但它仍然是递归。
对于递归算法，空间复杂度为O(N)，时间复杂度为O(N)。对于迭代算法，空间复杂度为 O(1)，时间复杂度为 O(N)。
但如果我们使用堆栈，复杂性方面的事情仍然是一样的。我认为只有尾递归才能转化为迭代。
这 堆栈和递归消除 文章捕捉了在堆上外部化堆栈帧的想法，但没有提供 简单且可重复 方式进行转换。下面是其中之一。
在转换为迭代代码时，必须意识到递归调用可能发生在任意深度的代码块中。它不仅仅是参数，还有返回待执行逻辑的点以及参与后续条件语句的变量状态，这很重要。下面是一种非常简单的方法，可以用最少的更改转换为迭代代码。
考虑这个递归代码：
struct tnode
{
tnode(int n) : data(n), left(0), right(0) {}
tnode *left, *right;
int data;
};
void insertnode_recur(tnode *node, int num)
{
if(node->data <= num)
{
if(node->right == NULL)
node->right = new tnode(num);
else
insertnode(node->right, num);
}
else
{
if(node->left == NULL)
node->left = new tnode(num);
else
insertnode(node->left, num);
}
}
迭代代码：
// Identify the stack variables that need to be preserved across stack
// invocations, that is, across iterations and wrap them in an object
struct stackitem
{
stackitem(tnode *t, int n) : node(t), num(n), ra(0) {}
tnode *node; int num;
int ra; //to point of return
};
void insertnode_iter(tnode *node, int num)
{
vector<stackitem> v;
//pushing a stackitem is equivalent to making a recursive call.
v.push_back(stackitem(node, num));
while(v.size())
{
// taking a modifiable reference to the stack item makes prepending
// 'si.' to auto variables in recursive logic suffice
// e.g., instead of num, replace with si.num.
stackitem &si = v.back();
switch(si.ra)
{
// this jump simulates resuming execution after return from recursive
// call
case 1: goto ra1;
case 2: goto ra2;
default: break;
}
if(si.node->data <= si.num)
{
if(si.node->right == NULL)
si.node->right = new tnode(si.num);
else
{
// replace a recursive call with below statements
// (a) save return point,
// (b) push stack item with new stackitem,
// (c) continue statement to make loop pick up and start
// processing new stack item,
// (d) a return point label
// (e) optional semi-colon, if resume point is an end
// of a block.
si.ra=1;
v.push_back(stackitem(si.node->right, si.num));
continue;
ra1: ;
}
}
else
{
if(si.node->left == NULL)
si.node->left = new tnode(si.num);
else
{
si.ra=2;
v.push_back(stackitem(si.node->left, si.num));
continue;
ra2: ;
}
}
v.pop_back();
}
}
请注意，代码的结构仍然保持递归逻辑，并且修改最少，从而减少了错误数量。为了进行比较，我用 ++ 和 -- 标记了更改。除了 v.push_back 之外，大多数新插入的块对于任何转换后的迭代逻辑都是通用的
void insertnode_iter(tnode *node, int num)
{
+++++++++++++++++++++++++
vector<stackitem> v;
v.push_back(stackitem(node, num));
while(v.size())
{
stackitem &si = v.back();
switch(si.ra)
{
case 1: goto ra1;
case 2: goto ra2;
default: break;
}
------------------------
if(si.node->data <= si.num)
{
if(si.node->right == NULL)
si.node->right = new tnode(si.num);
else
{
+++++++++++++++++++++++++
si.ra=1;
v.push_back(stackitem(si.node->right, si.num));
continue;
ra1: ;
-------------------------
}
}
else
{
if(si.node->left == NULL)
si.node->left = new tnode(si.num);
else
{
+++++++++++++++++++++++++
si.ra=2;
v.push_back(stackitem(si.node->left, si.num));
continue;
ra2: ;
-------------------------
}
}
+++++++++++++++++++++++++
v.pop_back();
}
-------------------------
}
在谷歌上搜索“延续传递风格”。有一个转换为尾递归样式的一般过程;还有一个将尾递归函数转变为循环的通用过程。
就是消磨时间...递归函数
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);
}
}
一般来说，递归函数避免堆栈溢出的技术称为蹦床技术，被 Java 开发人员广泛采用。
然而，对于 C# 有一个小辅助方法 这里 这会将您的递归函数转变为迭代函数，而无需更改逻辑或使代码难以理解。C# 是一种非常好的语言，用它可以实现令人惊奇的事情。
它的工作原理是用辅助方法包装方法的一部分。例如下面的递归函数：
int Sum(int index, int[] array)
{
//This is the termination condition
if (int >= array.Length)
//This is the returning value when termination condition is true
return 0;
//This is the recursive call
var sumofrest = Sum(index+1, array);
//This is the work to do with the current item and the
//result of recursive call
return array[index]+sumofrest;
}
变成：
int Sum(int[] ar)
{
return RecursionHelper<int>.CreateSingular(i => i >= ar.Length, i => 0)
.RecursiveCall((i, rv) => i + 1)
.Do((i, rv) => ar[i] + rv)
.Execute(0);
}
想想真正需要堆栈的东西：
如果我们将递归模式视为：
if(task can be done directly) {
return result of doing task directly
} else {
split task into two or more parts
solve for each part (possibly by recursing)
return result constructed by combining these solutions
}
比如经典的河内塔
if(the number of discs to move is 1) {
just move it
} else {
move n-1 discs to the spare peg
move the remaining disc to the target peg
move n-1 discs from the spare peg to the target peg, using the current peg as a spare
}
这可以转换为在显式堆栈上工作的循环，将其重新表述为：
place seed task on stack
while stack is not empty
take a task off the stack
if(task can be done directly) {
Do it
} else {
Split task into two or more parts
Place task to consolidate results on stack
Place each task on stack
}
}
对于河内塔，这变为：
stack.push(new Task(size, from, to, spare));
while(! stack.isEmpty()) {
task = stack.pop();
if(task.size() = 1) {
just move it
} else {
stack.push(new Task(task.size() -1, task.spare(), task,to(), task,from()));
stack.push(new Task(1, task.from(), task.to(), task.spare()));
stack.push(new Task(task.size() -1, task.from(), task.spare(), task.to()));
}
}
关于如何定义堆栈有相当大的灵活性。你可以让你的堆栈成为一个列表 Command 做复杂事情的对象。或者您可以反其道而行之，使其成为更简单类型的列表（例如一个“任务”可能是堆栈上的 4 个元素 int, ，而不是堆栈中的一个元素 Task).
所有这些意味着堆栈的内存位于堆中而不是 Java 执行堆栈中，但这很有用，因为您可以更好地控制它。
要寻找的一种模式是函数末尾的递归调用（所谓的尾递归）。这可以很容易地用一段时间替换。例如，函数 foo：
void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
foo(node->left);
foo(node->right);
}
以对 foo 的调用结束。这可以替换为：
void foo(Node* node)
{
while(node != NULL)
{
// Do something with node...
foo(node->left);
node = node->right;
}
}
这消除了第二次递归调用。
我刚刚赞成建议使用显式堆栈的答案，我认为这是正确的解决方案并且具有普遍适用性。
我的意思是你可以用它来转换迭代函数中的任何递归函数。只需检查递归调用中保存了哪些值，这些值是 有 成为递归函数的本地函数，并将调用替换为循环，将它们压入堆栈。当堆栈为空时，递归函数将终止。
我忍不住要说，每个递归函数都相当于不同数据类型上的迭代函数的证明，这是我大学时代最珍贵的记忆之一。那门课程（和教授）真正让我了解了计算机编程的含义。
A 问题 已关闭，因为该副本具有非常具体的数据结构：
该节点具有以下结构：
typedef struct {
int32_t type;
int32_t valueint;
double valuedouble;
struct cNODE *next;
struct cNODE *prev;
struct cNODE *child;
} cNODE;
递归删除函数如下所示：
void cNODE_Delete(cNODE *c) {
cNODE*next;
while (c) {
next=c->next;
if (c->child) {
cNODE_Delete(c->child)
}
free(c);
c=next;
}
}
一般来说，对于多次（甚至一次）调用自身的递归函数来说，并不总是可以避免堆栈。然而，对于这种特殊的结构，这是可能的。这个想法是将所有节点展平到一个列表中。这是通过将当前节点的 child 在顶行列表的末尾。
void cNODE_Delete (cNODE *c) {
cNODE *tmp, *last = c;
while (c) {
while (last->next) {
last = last->next; /* find last */
}
if ((tmp = c->child)) {
c->child = NULL; /* append child to last */
last->next = tmp;
tmp->prev = last;
}
tmp = c->next; /* remove current */
free(c);
c = tmp;
}
}
该技术可应用于任何可简化为具有确定性拓扑排序的 DAG 的数据链接结构。当前节点子节点会重新排列，以便最后一个子节点采用所有其他子节点。然后可以删除当前节点，然后遍历可以迭代到剩余的子节点。
递归只不过是从一个函数调用另一个函数的过程，只是这个过程是通过调用函数本身来完成的。我们知道，当一个函数调用另一个函数时，第一个函数会保存其状态（其变量），然后将控制权传递给被调用的函数。被调用函数可以使用相同名称的变量来调用，例如 fun1(a) 可以调用 fun2(a)。当我们进行递归调用时，不会发生任何新的事情。一个函数通过将相同类型和名称相似的变量（但显然变量中存储的值不同，只有名称保持不变）传递给自身来调用自身。但在每次调用之前，该函数都会保存其状态，并且保存过程会继续进行。保存是在堆栈上完成的。
现在堆栈开始发挥作用。
因此，如果您编写一个迭代程序，每次将状态保存在堆栈中，然后在需要时从堆栈中弹出值，那么您已经成功地将递归程序转换为迭代程序！
证明很简单且具有分析性。
在递归中，计算机维护一个堆栈，在迭代版本中，您必须手动维护堆栈。
想一想，只需将深度优先搜索（图上）递归程序转换为 dfs 迭代程序即可。
一切顺利！
系统如何获取任何递归函数并使用堆栈执行它的粗略描述：
这旨在展示没有细节的想法。考虑这个将打印出图的节点的函数：
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 行的函数调用。show（B） 表示 - 将项目添加到堆栈中，意思是“您需要在第 2 行继续，局部变量状态 node=A” - 转到第 0 行，node=B。
为了执行代码，系统运行指令。当遇到函数调用时，系统会推送需要返回到原来位置的信息，运行函数代码，当函数完成时，会弹出有关需要转到哪里才能继续的信息。
这 关联 提供了一些解释并提出了保留“位置”的想法，以便能够到达几次递归调用之间的确切位置：
然而，所有这些示例都描述了递归调用的场景 固定的 次数。当你遇到以下情况时，事情会变得更加棘手：
function rec(...) {
for/while loop {
var x = rec(...)
// make a side effect involving return value x
}
}
有一种将递归遍历转换为迭代器的通用方法，即使用连接多个迭代器提供者的惰性迭代器（返回迭代器的 lambda 表达式）。看我的 将递归遍历转换为迭代器.
使用堆栈将递归函数转变为迭代函数的另一个简单而完整的示例。
#include <iostream>
#include <stack>
using namespace std;
int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }
struct Par
{
int a, b;
Par() : Par(0, 0) {}
Par(int _a, int _b) : a(_a), b(_b) {}
};
int GCDIter(int a, int b)
{
stack<Par> rcstack;
if (b == 0)
return a;
rcstack.push(Par(b, a % b));
Par p;
while (!rcstack.empty())
{
p = rcstack.top();
rcstack.pop();
if (p.b == 0)
continue;
rcstack.push(Par(p.b, p.a % p.b));
}
return p.a;
}
int main()
{
//cout << GCD(24, 36) << endl;
cout << GCDIter(81, 36) << endl;
cin.get();
return 0;
}
