从递归到迭代的方法

Question

从递归到迭代的方法

在我多年的编程中，我经常使用递归来解决简单的问题，但我完全意识到，有时由于内存/速度问题，您需要迭代。

所以，在很久以前的某个时候，我试着去寻找是否存在任何“模式”或教科书方法来将一种常见的递归方法转换为迭代，却一无所获。或者至少我记忆中的任何东西都不会有帮助。

• 有一般规则吗？
• 有“模式”吗？

Answer 1

通常，我将通常传递给递归函数的参数推送到堆栈中，从而将递归算法替换为迭代算法。实际上，您正在将程序堆栈替换为您自己的程序堆栈。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);

Answer 2

实际上，最常见的方法是保留自己的堆栈。下面是C中的递归快速排序函数：void&nbsp;quicksort(int*&nbsp;array,&nbsp;int&nbsp;left,&nbsp;int&nbsp;right) { &nbsp;&nbsp;&nbsp;&nbsp;if(left&nbsp;>=&nbsp;right) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;return; &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;index&nbsp;=&nbsp;partition(array,&nbsp;left,&nbsp;right); &nbsp;&nbsp;&nbsp;&nbsp;quicksort(array,&nbsp;left,&nbsp;index&nbsp;-&nbsp;1); &nbsp;&nbsp;&nbsp;&nbsp;quicksort(array,&nbsp;index&nbsp;+&nbsp;1,&nbsp;right); }下面是如何通过保留自己的堆栈来使其迭代的方法：void&nbsp;quicksort(int&nbsp;*array,&nbsp;int&nbsp;left,&nbsp;int&nbsp;right) { &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;stack[1024]; &nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;i=0; &nbsp;&nbsp;&nbsp;&nbsp;stack[i++]&nbsp;=&nbsp;left; &nbsp;&nbsp;&nbsp;&nbsp;stack[i++]&nbsp;=&nbsp;right; &nbsp;&nbsp;&nbsp;&nbsp;while&nbsp;(i&nbsp;>&nbsp;0) &nbsp;&nbsp;&nbsp;&nbsp;{ &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;right&nbsp;=&nbsp;stack[--i]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;left&nbsp;=&nbsp;stack[--i]; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;if&nbsp;(left&nbsp;>=&nbsp;right) &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;continue; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;int&nbsp;index&nbsp;=&nbsp;partition(array,&nbsp;left,&nbsp;right); &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stack[i++]&nbsp;=&nbsp;left; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stack[i++]&nbsp;=&nbsp;index&nbsp;-&nbsp;1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stack[i++]&nbsp;=&nbsp;index&nbsp;+&nbsp;1; &nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;&nbsp;stack[i++]&nbsp;=&nbsp;right; &nbsp;&nbsp;&nbsp;&nbsp;} }显然，这个例子不检查堆栈边界.。实际上，您可以根据给定的左、右值的最坏情况对堆栈进行大小调整。但你知道这个主意。

Answer 3

似乎没有人讨论递归函数在主体中多次调用自己的位置，并处理返回到递归中的特定点(即不是原始递归)的问题。据说每个递归都可以转化为迭代。看来这是可能的。我只是想出了一个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();             }         }