从recursion到迭代的方法

为了解决简单的问题,我在编程上花了很多年的时间用了很多recursion,但是我完全意识到有时候由于内存/速度的问题需要迭代

所以,在很久以前的某个时候,我去试图找出是否有任何“模式”或文本书的方式来改变一个共同的recursion方法迭代,什么也没有发现。 或者至less没有什么,我能记得它会帮助。

  • 有一般规定吗?
  • 有没有“模式”?

18 Solutions collect form web for “从recursion到迭代的方法”

通常,我通过迭代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遍历到迭代器 。

  • F#vs OCaml:堆栈溢出
  • 如何创build一个MySQL分层recursion查询
  • 如何在Twig中渲染一棵树
  • multidimensional array迭代
  • 用列表返回Pythonrecursion无
  • 在Java中使用recursion的因子
  • Pythonrecursion和返回语句
  • 什么是paramorphisms?
  • 了解recursion函数如何工作
  • DataAnnotations:recursionvalidation整个对象图
  • 给定的股票报价最大化利润