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

所以,在很久以前的某个时候,我去尝试寻找是否存在任何“模式”或教科书上的方法来将常见的递归方法转换为迭代,但一无所获。至少我想不起有什么帮助。

有一般的规则吗? 有“模式”吗?


当前回答

这个链接提供了一些解释,并提出了保持“位置”的想法,以便能够在几个递归调用之间到达确切的位置:

但是,所有这些示例都描述了递归调用进行固定次数的场景。当你遇到以下情况时,事情就变得棘手了:

function rec(...) {
  for/while loop {
    var x = rec(...)
    // make a side effect involving return value x
  }
}

其他回答

想想那些真正需要堆栈的东西:

如果我们考虑递归的模式为:

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对象列表,这些对象可以做一些复杂的事情。或者你可以走相反的方向,让它成为一个简单类型的列表(例如,一个“task”可能是一个int堆栈上的4个元素,而不是一个task堆栈上的一个元素)。

这意味着堆栈的内存在堆中,而不是在Java执行堆栈中,但这可能很有用,因为您可以更好地控制它。

通常避免栈溢出的技术是递归函数,称为蹦床技术,被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);
}

努力使你的递归调用尾部递归(递归的最后一个语句是递归调用)。一旦你有了它,将它转换为迭代通常是相当容易的。

似乎没有人指出递归函数在主体中调用自己超过一次的位置,并处理返回递归中的特定点(即不是原始递归)。据说每一个递归都可以转化为迭代,所以这似乎是可能的。

我刚刚想出了一个如何做到这一点的c#示例。假设您有以下递归函数,它的作用类似于poststorder遍历,AbcTreeNode是一个带有指针a、b、c的3元树。

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


        }

这个链接提供了一些解释,并提出了保持“位置”的想法,以便能够在几个递归调用之间到达确切的位置:

但是,所有这些示例都描述了递归调用进行固定次数的场景。当你遇到以下情况时,事情就变得棘手了:

function rec(...) {
  for/while loop {
    var x = rec(...)
    // make a side effect involving return value x
  }
}