从递归到迭代的方法

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 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;
    }
}

显然，这个例子不检查堆栈边界.。实际上，您可以根据给定的左、右值的最坏情况对堆栈进行大小调整。但你知道这个主意。

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();
            }


        }