从递归到迭代

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

在谷歌中搜索“延续传递样式”。有一个转换为尾部递归样式的一般过程;还有一个将尾部递归函数转换为循环的通用过程。

要寻找的一种模式是函数末尾的递归调用(所谓的尾部递归)。这很容易用一段时间来代替。例如，函数foo:

void foo(Node* node)
{
if(node == NULL)
return;
// Do something with node...
foo(node->left);
foo(node->right);
}

以调用foo结束。这可以替换为:

void foo(Node* node)
{
while(node != NULL)
{
// Do something with node...
foo(node->left);
node = node->right;
}
}

这消除了第二次递归调用。

一般来说，通过简单地使用存储变量，可以将递归模拟为迭代。注意，递归和迭代通常是等价的;其中一种几乎总是可以转化为另一种。尾递归函数很容易转化为迭代函数。只需要将累加器变量设置为局部变量，并迭代而不是递归。下面是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;
}

据我所知，我可能在代码中犯了一个错误，但想法是存在的。

实际上，最常见的方法是保留自己的堆栈。下面是一个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;
}
}

显然，这个例子没有检查堆栈边界……实际上，你可以根据最坏的情况来确定堆栈的大小。但你懂的。

通常，通过将通常传递给递归函数的参数推入堆栈，我将递归算法替换为迭代算法。事实上，您正在用自己的程序堆栈替换程序堆栈。

var stack = [];
stack.push(firstObject);


// while not empty
while (stack.length) {


// Pop off end of stack.
obj = stack.pop();


// Do stuff.
// Push other objects on the stack as needed.
...


}

注意:如果你在里面有多个递归调用，并且你想要保留调用的顺序，你必须以相反的顺序将它们添加到堆栈:

foo(first);
foo(second);

必须由

stack.push(second);
stack.push(first);

编辑:文章栈和递归消除(或备份链接)将详细介绍这个主题。

即使使用堆栈也不能将递归算法转换为迭代算法。普通的递归是基于函数的递归，如果我们使用堆栈，那么它就变成了基于堆栈的递归。但它仍然是递归。

但是如果我们使用堆栈的话复杂度还是一样的。我认为只有尾递归可以转化为迭代。

只是消磨时间……递归函数

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


}

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

我刚刚想出了一个如何做到这一点的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();
}




}

现在堆栈开始发挥作用了。

因此，如果您编写了一个迭代程序，并每次将状态保存在堆栈上，然后在需要时从堆栈中弹出值，那么您已经成功地将递归程序转换为迭代程序!

证明是简单而分析的。

在递归中，计算机维护堆栈，而在迭代版本中，您将不得不手动维护堆栈。

仔细想想，只需将深度优先搜索(在图上)递归程序转换为dfs迭代程序。

祝你一切顺利!

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

栈和递归消除文章抓住了在堆上外部化堆栈帧的思想，但没有提供直接且可重复转换方法。下面是一个。

在转换为迭代代码时，必须意识到递归调用可能发生在任意深度的代码块中。它不仅是参数，而且是返回到仍然要执行的逻辑的点，以及参与后续条件的变量的状态，这很重要。下面是一种转换为迭代代码的非常简单的方法。

考虑下面的递归代码:

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
// e.g., 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();
}
}

请注意，代码的结构仍然保持忠于递归逻辑，并且修改是最小的，从而减少了错误的数量。为了便于比较，我用++和——标记了更改。除了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();
}

-------------------------

}

一个系统如何接受任何递归函数并使用堆栈执行它的粗略描述:

这是为了在没有细节的情况下展示想法。考虑这个函数，它将打印出图的节点:

function show(node)
0. if isleaf(node):
1.  print node.name
2. else:
3.  show(node.left)
4.  show(node)
5.  show(node.right)

函数调用意味着保存本地状态和延续点，以便返回，然后跳转到要调用的函数。

例如，假设show(A)开始运行。函数调用在第3行。显示(B)的意思 -将项目添加到堆栈，意思是“你需要在第2行继续使用本地变量状态node=A” -到第0行，节点为b

为了执行代码，系统运行指令。当遇到函数调用时，系统将需要的信息推回到原来的位置，运行函数代码，当函数完成时，弹出关于需要继续执行的位置的信息。

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

然而，所有这些例子都描述了递归调用次数为固定的场景。当你遇到以下情况时，事情就变得棘手了:

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

问题被关闭为this的副本，它有一个非常特定的数据结构:

节点结构如下:

typedef struct {
int32_t type;
int32_t valueint;
double  valuedouble;
struct  cNODE *next;
struct  cNODE *prev;
struct  cNODE *child;
} cNODE;

递归删除函数如下所示:

void cNODE_Delete(cNODE *c) {
cNODE*next;
while (c) {
next=c->next;
if (c->child) {
cNODE_Delete(c->child)
}
free(c);
c=next;
}
}

一般来说，对于多次(甚至一次)调用自身的递归函数，避免使用堆栈并不总是可能的。然而，对于这种特殊的结构，这是可能的。其思想是将所有节点平展为单个列表。这是通过将当前节点的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;
}
}

这种技术可以应用于任何可以简化为具有确定性拓扑顺序的DAG的数据链接结构。当前节点子节点被重新排列，以便最后一个子节点采用所有其他子节点。然后可以删除当前节点，然后遍历可以迭代到剩余的子节点。

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

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

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执行堆栈中，但这可能很有用，因为您可以更好地控制它。

有一种将递归遍历转换为迭代器的通用方法，即使用连接多个迭代器提供者的惰性迭代器(返回迭代器的lambda表达式)。请看我的将递归遍历转换为迭代器。

另一个使用堆栈将递归函数转换为迭代函数的简单而完整的示例。

#include <iostream>
#include <stack>
using namespace std;


int GCD(int a, int b) { return b == 0 ? a : GCD(b, a % b); }


struct Par
{
int a, b;
Par() : Par(0, 0) {}
Par(int _a, int _b) : a(_a), b(_b) {}
};


int GCDIter(int a, int b)
{
stack<Par> rcstack;


if (b == 0)
return a;
rcstack.push(Par(b, a % b));


Par p;
while (!rcstack.empty())
{
p = rcstack.top();
rcstack.pop();
if (p.b == 0)
continue;
rcstack.push(Par(p.b, p.a % p.b));
}


return p.a;
}


int main()
{
//cout << GCD(24, 36) << endl;
cout << GCDIter(81, 36) << endl;


cin.get();
return 0;
}

我的例子是用Clojure编写的，但是应该很容易翻译成任何语言。

给定这个函数，StackOverflows用于n的大值:

(defn factorial [n]
(if (< n 2)
1
(*' n (factorial (dec n)))))

我们可以用以下方式定义一个使用自己堆栈的版本:

(defn factorial [n]
(loop [n n
stack []]
(if (< n 2)
(return 1 stack)
;; else loop with new values
(recur (dec n)
;; push function onto stack
(cons (fn [n-1!]
(*' n n-1!))
stack)))))

其中return定义为:

(defn return
[v stack]
(reduce (fn [acc f]
(f acc))
v
stack))

这也适用于更复杂的函数，例如阿克曼函数:

(defn ackermann [m n]
(cond
(zero? m)
(inc n)


(zero? n)
(recur (dec m) 1)


:else
(recur (dec m)
(ackermann m (dec n)))))

可以转化为:

(defn ackermann [m n]
(loop [m m
n n
stack []]
(cond
(zero? m)
(return (inc n) stack)


(zero? n)
(recur (dec m) 1 stack)


:else
(recur m
(dec n)
(cons #(ackermann (dec m) %)
stack)))))

这是一个老问题，但我想添加一个不同的方面作为解决方案。我目前正在做一个项目，在这个项目中我使用了c#的泛滥填充算法。通常，我首先用递归实现这个算法，但很明显，它导致了堆栈溢出。之后，我将方法从递归改为迭代。是的，它工作了，我不再得到堆栈溢出错误。但这一次，由于我将洪水填充方法应用于非常大的结构，程序进入了一个无限循环。出于这个原因，我想到函数可能重新进入了它已经访问过的地方。为了解决这个问题，我决定使用字典来记录访问点。如果该节点(x,y)已经第一次添加到堆栈结构中，则该节点(x,y)将作为键保存在字典中。即使稍后尝试再次添加相同的节点，它也不会被添加到堆栈结构中，因为该节点已经在字典中。让我们看看伪代码:

startNode = pos(x,y)


Stack stack = new Stack();


Dictionary visited<pos, bool> = new Dictionary();


stack.Push(startNode);


while(stack.count != 0){
currentNode = stack.Pop();
if "check currentNode if not available"
continue;
if "check if already handled"
continue;
else if "run if it must be wanted thing should be handled"
// make something with pos currentNode.X and currentNode.X
        

// then add its neighbor nodes to the stack to iterate
// but at first check if it has already been visited.
        

if(!visited.Contains(pos(x-1,y)))
visited[pos(x-1,y)] = true;
stack.Push(pos(x-1,y));
if(!visited.Contains(pos(x+1,y)))
...
if(!visited.Contains(pos(x,y+1)))
...
if(!visited.Contains(pos(x,y-1)))
...
}

TLDR

您可以比较下面的源代码，在不阅读整个答案的情况下直观地理解这种方法。

我在使用一些多键快速排序代码来处理非常大的文本块以生成后缀数组时遇到了问题。由于所需的递归深度太深，代码将中止。通过这种方法，终止问题得到了解决。转换后，一些作业所需的最大帧数可以被捕获，在10K到100K之间，占用1M到6M的内存。这不是最优的解决方案，有更有效的方法来生成后缀数组。不管怎样，这是我们使用的方法。

的方法

将递归函数转换为适用于任何情况的迭代解决方案的一般方法是模拟本机编译代码在函数调用期间使用的过程和调用返回的过程。

举一个需要一些复杂方法的例子，我们有多键快速排序算法。这个函数有三个连续的递归调用，每次调用之后，执行从下一行开始。

函数的状态在堆栈帧中被捕获，并被推入执行堆栈。当sort()从自身内部调用并返回时，将恢复调用时的堆栈帧。这样，所有变量的值都与调用之前相同——除非调用修改了它们。

递归函数

def sort(a: list_view, d: int):
if len(a) <= 1:
return
p = pivot(a, d)
i, j = partition(a, d, p)
sort(a[0:i], d)
sort(a[i:j], d + 1)
sort(a[j:len(a)], d)

采用这个模型，并模仿它，设置一个列表来充当堆栈。在这个例子中，元组被用来模拟帧。如果这是用C编码的，就可以使用结构体。数据可以包含在数据结构中，而不是一次只推入一个值。

重新实现为“迭代”;

# Assume `a` is view-like object where slices reference
# the same internal list of strings.


def sort(a: list_view):
stack = []
stack.append((LEFT, a, 0))                  # Initial frame.


while len(stack) > 0:
frame = stack.pop()


if len(frame[1]) <= 1:                  # Guard.
continue


stage = frame[0]                        # Where to jump to.


if stage == LEFT:
_, a, d = frame                     # a - array/list, d - depth.
p = pivot(a, d)
i, j = partition(a, d, p)
stack.append((MID, a, i, j, d))     # Where to go after "return".
stack.append((LEFT, a[0:i], d))     # Simulate function call.


elif stage == MID:                      # Picking up here after "call"
_, a, i, j, d = frame               # State before "call" restored.
stack.append((RIGHT, a, i, j, d))   # Set up for next "return".
stack.append((LEFT, a[i:j], d + 1)) # Split list and "recurse".


elif stage == RIGHT:
_, a, _, j, d = frame
stack.append((LEFT, a[j:len(a)], d)


else:
pass

当调用函数时，关于函数返回后在何处开始执行的信息包含在堆栈帧中。在本例中，if/elif/else块表示调用返回后开始执行的点。在C语言中，这可以实现为switch语句。

在这个例子中，块被赋予了标签;它们是根据列表在每个块中的分区方式任意标记的。第一个方块，&;LEFT"在左侧拆分列表。“MID"Section表示在中间分割列表的块，等等。

使用这种方法，模拟调用需要两个步骤。首先，一个帧被推入堆栈，这将导致执行在当前块后面的&;call&;“returns"。帧中的值指示在"call"后面的循环中if/elif/else节落入哪个部分。

然后“呼叫”;帧被推入堆栈。对于这个特定的例子，在大多数情况下，这会将执行发送到第一个"LEFT"块。这是实际排序完成的地方，而不管列表的哪一部分被分割到那里。

在循环开始之前，推到函数顶部的主帧表示初始调用。然后在每次迭代中，弹出一个帧。“左/中期/ RIGHT"value/label用于落入if/elif/else语句的正确块中。该帧用于恢复当前操作所需变量的状态，然后在下一次迭代时弹出返回帧，将执行发送到后续部分。

返回值

如果递归函数返回自己使用的值，则可以将其与其他变量同等对待。只需在堆栈框架中为它创建一个字段。如果a "callee"返回一个值，它检查堆栈，看它是否有任何项;如果是，则更新堆栈顶部帧中的返回值。对于这个你可以看看另一个例子的例子，用同样的方法进行递归到迭代的转换。

结论

像这样将递归函数转换为迭代函数的方法，本质上也是“递归”的。而不是将流程堆栈用于实际的函数调用，取而代之的是另一个通过编程实现的堆栈。

得到了什么?也许在速度上有一些微不足道的改进。或者，它可以作为一种绕过某些编译器和/或执行环境施加的堆栈限制的方法(堆栈指针击中保护页面)。在某些情况下，可以减少推送到堆栈上的数据量。通过模仿递归实现自动得到的东西，所获得的收益是否抵消了代码中引入的复杂性?

在排序算法的情况下，找到一种方法来实现这个特定的堆栈可能是具有挑战性的，加上有很多迭代排序算法可用得更快。据说任何递归算法都可以迭代地实现。确定……但是有些算法如果没有修改到不再是同一种算法的程度，就不能很好地转换。

仅仅为了转换递归算法而转换递归算法可能不是一个好主意。无论如何，无论如何，上面的方法是一种通用的转换方式，应该适用于任何东西。

如果您发现确实需要递归函数的迭代版本，并且不使用自己的内存消耗堆栈，那么最好的方法可能是放弃代码并使用学术文章中的描述编写自己的代码，或者在纸上完成它，然后从头开始编码，或者其他基础方法。