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

要寻找的一种模式是函数末尾的递归调用(所谓的尾部递归)。这很容易用一段时间来代替。例如，函数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语言的递归快速排序函数:

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

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

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

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

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

This is an old question but I want to add a different aspect as a solution. I'm currently working on a project in which I used the flood fill algorithm using C#. Normally, I implemented this algorithm with recursion at first, but obviously, it caused a stack overflow. After that, I changed the method from recursion to iteration. Yes, It worked and I was no longer getting the stack overflow error. But this time, since I applied the flood fill method to very large structures, the program was going into an infinite loop. For this reason, it occurred to me that the function may have re-entered the places it had already visited. As a definitive solution to this, I decided to use a dictionary for visited points. If that node(x,y) has already been added to the stack structure for the first time, that node(x,y) will be saved in the dictionary as the key. Even if the same node is tried to be added again later, it won't be added to the stack structure because the node is already in the dictionary. Let's see on pseudo-code:

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