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 show(node)
0. if isleaf(node):
1.  print node.name
2. else:
3.  show(node.left)
4.  show(node)
5.  show(node.right)

例如图表: A - B > C - > show(A)将打印B, A, C

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

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

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

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

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

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

节点结构如下:

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

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

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


        }