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

对于递归算法，空间复杂度为O(N)，时间复杂度为O(N)。 对于迭代算法，空间复杂度为O(1)，时间复杂度为O(N)。

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

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

结论

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

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

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

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

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

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

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

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

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

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

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

节点结构如下:

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++中的一个例子(如果不使用默认参数的话):

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

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