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

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

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

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

TLDR

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

I ran into issues with some multi-key quicksort code I was using to process very large blocks of text to produce suffix arrays. The code would abort due to the extreme depth of recursion required. With this approach, the termination issues were resolved. After conversion the maximum number of frames required for some jobs could be captured, which was between 10K and 100K, taking from 1M to 6M memory. Not an optimum solution, there are more effective ways to produce suffix arrays. But anyway, here's the approach used.

的方法

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

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

函数的状态在堆栈帧中被捕获，并被推入执行堆栈。当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”部分表示在中间分割列表的块，等等。

使用这种方法，模拟调用需要两个步骤。首先，一个帧被推入堆栈，这将导致在“调用”“返回”后在当前块后面恢复执行。帧中的值表示在“调用”之后的循环中进入哪个if/elif/else节。

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

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

返回值

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

结论

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

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

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

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

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

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

节点结构如下:

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

一般来说，对于多次(甚至一次)调用自身的递归函数，避免使用堆栈并不总是可能的。然而，对于这种特殊的结构，这是可能的。其思想是将所有节点平展为单个列表。这是通过将当前节点的子节点放在顶部行列表的末尾来实现的。

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的数据链接结构。当前节点子节点被重新排列，以便最后一个子节点采用所有其他子节点。然后可以删除当前节点，然后遍历可以迭代到剩余的子节点。

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

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

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