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

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

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

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

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

}

Recursion is nothing but the process of calling of one function from the other only this process is done by calling of a function by itself. As we know when one function calls the other function the first function saves its state(its variables) and then passes the control to the called function. The called function can be called by using the same name of variables ex fun1(a) can call fun2(a). When we do recursive call nothing new happens. One function calls itself by passing the same type and similar in name variables(but obviously the values stored in variables are different,only the name remains same.)to itself. But before every call the function saves its state and this process of saving continues. The SAVING IS DONE ON A STACK.

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

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

证明是简单而分析的。

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

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

祝你一切顺利!

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”返回一个值，它会检查堆栈，看它是否有任何条目;如果是，则更新堆栈顶部帧中的返回值。关于这个的例子，你可以看看另一个同样方法的递归到迭代转换的例子。

结论

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

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

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

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

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

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

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

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

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