从recursion到迭代的方法
为了解决简单的问题，我在编程上花了很多年的时间用了很多recursion，但是我完全意识到有时候由于内存/速度的问题需要迭代。
所以，在很久以前的某个时候，我去试图找出是否有任何“模式”或文本书的方式来改变一个共同的recursion方法迭代，什么也没有发现。 或者至less没有什么，我能记得它会帮助。
- 有一般规定吗？
- 有没有“模式”？
通常，我通过迭代algorithm将通常传递给recursion函数的参数推送到堆栈上来replacerecursionalgorithm。 事实上，你正在用自己的方法来replace程序堆栈。
Stack<Object> stack; stack.push(first_object); while( !stack.isEmpty() ) { // Do something my_object = stack.pop(); // Push other objects on the stack. } 注意：如果你有多个recursion调用，并且你想保留调用的顺序，你必须按照相反的顺序将它们添加到堆栈中：
foo(first); foo(second);
必须被replace
stack.push(second); stack.push(first);
编辑：文章堆栈和recursion抵消 （或文章备份链接 ）进入这个问题的更多细节。
真的，最常见的做法是保留自己的堆栈。 这是一个recursion的快速sortingfunction在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; } }
显然，这个例子并不检查堆栈边界，而是真的可以根据给定的左值和右值的最坏情况确定堆栈的大小。 但是你明白了。
似乎没有人已经解决了recursion函数在本体中多次调用自身的地方，并且处理返回到recursion中的特定点（即不是原始recursion）。 据说每一次recursion都可以转化为迭代 ，所以看来这应该是可能的。
我刚刚提出了一个C＃如何做到这一点的例子。 假设你有下面的recursion函数，就像后序遍历一样，AbcTreeNode是一个三叉树，指针为a，b，c。
public static void AbcRecursiveTraversal(this AbcTreeNode x, List<int> list) { if (x != null) { AbcRecursiveTraversal(xa, list); AbcRecursiveTraversal(xb, list); AbcRecursiveTraversal(xc, list); list.Add(x.key);//finally visit root } }
迭代解决scheme：
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 = xa; address = A; break; case B: stack.Push(x); stack.Push(C); x = xb; address = A; break; case C: stack.Push(x); stack.Push(null); x = xc; address = A; break; case null: list_iterative.Add(x.key); @return = true; break; } } if (@return == true) { address = (int?)stack.Pop(); x = (AbcTreeNode)stack.Pop(); } }
努力使你的recursion调用尾recursion （recursion最后一个语句是recursion调用）。 一旦你有了，把它转换成迭代通常很容易。
那么，一般来说，recursion可以通过简单地使用一个存储variables来模仿迭代。 请注意，recursion和迭代通常是等价的; 几乎总是可以转换为另一个。 尾recursion函数很容易转换为迭代函数。 只要使累加器variables为本地variables，并迭代而不是recursion。 这是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; }
了解我，我可能在代码中犯了一个错误，但是这个想法就在那里。
即使使用堆栈也不会将recursionalgorithm转换为迭代。 正常的recursion是基于函数的recursion，如果我们使用堆栈，那么它就成为基于堆栈的recursion。 但它仍然recursion。
对于recursionalgorithm，空间复杂度为O（N），时间复杂度为O（N）。 对于迭代algorithm，空间复杂度为O（1），时间复杂度为O（N）。
但是，如果我们使用堆栈的复杂性方面保持不变。 我认为只有尾部recursion可以转换为迭代。
堆栈和recursion消除文章捕捉堆栈外部化堆栈框架的想法，但不提供直接和可重复的方式来转换。 下面是一个。
在转换为迭代代码时，必须意识到recursion调用可能发生在任意深度的代码块中。 它不仅仅是参数，还包括返回到要执行的逻辑和参与随后的条件的variables的状态。 下面是一个非常简单的方法，以最小的改变转换成迭代代码。
考虑这个recursion的代码：
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 // eg, 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(); } }
注意代码的结构对于recursion逻辑仍然是真实的，并且修改是最小的，从而导致更less的错误。 为了比较，我用++和 – 标记了这些变化。 除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(); }
-------------------------
}
search谷歌的“继续传递风格”。 有一个转换为尾recursion风格的一般程序; 还有一个把尾recursion函数转换成循环的一般过程。
通常避免堆栈溢出的技术是recursion函数，被称为蹦床技术，被Java开发人员广泛采用。
但是，对于C＃来说，这里有一个小的帮助器方法，可以将recursion函数转换为迭代，而不需要更改逻辑或使代码不可理解。 C＃是一个非常好的语言，它可以让人惊叹。
它通过用辅助方法包装部分方法来工作。 例如下面的recursion函数：
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); }
只要消磨时间…recursion函数
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); } }
要查找的一种模式是函数末尾的recursion调用（所谓的尾recursion）。 这可以很容易地被replace一段时间。 例如，函数foo：
void foo(Node* node) { if(node == NULL) return; // Do something with node... foo(node->left); foo(node->right); }
以foo调用结束。 这可以被replace为：
void foo(Node* node) { while(node != NULL) { // Do something with node... foo(node->left); node = node->right; } }
这消除了第二次recursion调用。
我刚刚提出了一个答案，build议使用一个明确的堆栈，我认为这是正确的解决scheme，具有普遍的适用性。
我的意思是你可以使用它来转换迭代函数中的任何recursion函数。 只要检查recursion调用中保存哪些值，那些必须是recursion函数的本地值，然后用一个循环replace这些调用，然后将它们压入堆栈。 当堆栈为空时，recursion函数将被终止。
我无法抗拒地说，每一个recursion函数都等价于一个不同数据types的迭代函数，这是我大学时代的一个最珍贵的记忆。 这是真正让我明白计算机编程是关于什么的课程（和教授）。
recursion不过是从另一个函数调用另一个函数的过程，只有通过调用函数本身才能完成。 正如我们所知，当一个函数调用另一个函数时，第一个函数会保存其状态（variables），然后将控制权交给被调用的函数。 被调用函数可以通过使用相同名称的variables来调用，例如fun1（a）可以调用fun2（a）。 当我们做recursion调用时，没有新的事情发生。 一个函数通过在名称variables中传递相同的types和类似的名称（但显然存储在variables中的值不同，只有名称保持不变）。 但在每次调用之前，函数都会保存其状态，并继续保存这个过程。 节省是在一个堆栈上完成的。
现在，堆栈进入游戏。
所以，如果你编写一个迭代程序，并且每次将这个状态保存在一个堆栈上，然后在需要的时候从堆栈中popup这些值，那么你已经成功地将一个recursion程序转换为一个迭代程序了！
certificate是简单和分析的。
在recursion中，计算机维护堆栈，在迭代版本中，您将不得不手动维护堆栈。
考虑一下，只需将深度优先search（在图上）recursion程序转换为dfs迭代程序即可。
祝一切顺利！
作为这个问题的一个重复的问题有一个非常具体的数据结构：
该节点具有以下结构：
typedef struct { int32_t type; int32_t valueint; double valuedouble; struct cNODE *next; struct cNODE *prev; struct cNODE *child; } cNODE;
recursion删除function如下所示：
void cNODE_Delete(cNODE *c) { cNODE*next; while (c) { next=c->next; if (c->child) { cNODE_Delete(c->child) } free(c); c=next; } }
一般来说，避免一次一次（甚至一次）调用自身的recursion函数的堆栈并不总是可能的。 但是，对于这个特定的结构，这是可能的。 这个想法是把所有的节点压缩成一个单一的列表。 这是通过将当前节点的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; } }
这种技术可以应用于任何可以通过确定性拓扑sorting缩减为DAG的数据链接结构。 当前节点的孩子被重新排列，以便最后一个孩子能够接纳所有其他的孩子。 然后，当前节点可以被删除，遍历可以迭代到剩下的孩子。
系统如何使用recursion函数并使用堆栈执行它的粗略描述：
这旨在表明没有细节的想法。 考虑这个函数将打印出一个图的节点：
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 A-> C显示（A）会打印B，A，C
函数调用意味着保存本地状态和继续点，以便返回，然后跳转要调用的函数。
例如，假设show（A）开始运行。 show（B）表示 – 将项目添加到堆栈，意思是“您将需要在局部variables状态node = A的第2行继续” – 转到line 0，node = B。
为了执行代码，系统运行指令。 遇到函数调用时，系统会将所需的信息推回到原来的位置，运行函数代码，函数完成后会popup关于需要继续的位置的信息。
这个链接提供了一些解释，并提出了保持“位置”能够到达几个recursion调用之间的确切位置的想法：
但是，所有这些例子都描述了recursion调用被固定的时间量的情况。 事情变得棘手，当你有这样的事情：
function rec(...) { for/while loop { var x = rec(...) // make a side effect involving return value x } }
思考事实上需要一个堆栈：
如果我们把recursion模式看作：
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对象。 或者你可以走相反的方向，使它成为一个简单types的列表（例如，一个“任务”可能是一个int堆栈中的4个元素，而不是Task栈中的一个元素）。
所有这一切意味着堆栈的内存在堆中，而不是在Java执行堆栈中，但是这对于您有更多的控制权是有用的。
有一种通过使用连接多个迭代器供应器（返回迭代器的lambdaexpression式）的惰性迭代器将recursion遍历转换为迭代器的一般方法。 看到我的转换recursion遍历到迭代器 。
