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

结论

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

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

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

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

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

我的例子是用Clojure编写的，但是应该很容易翻译成任何语言。

给定这个函数，当n值较大时StackOverflows:

(defn factorial [n]
  (if (< n 2)
    1
    (*' n (factorial (dec n)))))

我们可以用以下方式定义一个使用自己堆栈的版本:

(defn factorial [n]
  (loop [n n
         stack []]
    (if (< n 2)
      (return 1 stack)
      ;; else loop with new values
      (recur (dec n)
             ;; push function onto stack
             (cons (fn [n-1!]
                     (*' n n-1!))
                   stack)))))

其中return定义为:

(defn return
  [v stack]
  (reduce (fn [acc f]
            (f acc))
          v
          stack))

这也适用于更复杂的函数，例如阿克曼函数:

(defn ackermann [m n]
  (cond
    (zero? m)
    (inc n)

    (zero? n)
    (recur (dec m) 1)

    :else
    (recur (dec m)
           (ackermann m (dec n)))))

可以转化为:

(defn ackermann [m n]
  (loop [m m
         n n
         stack []]
    (cond
      (zero? m)
      (return (inc n) stack)

      (zero? n)
      (recur (dec m) 1 stack)

      :else
      (recur m
             (dec n)
             (cons #(ackermann (dec m) %)
                   stack)))))

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

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

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

一般来说，通过简单地使用存储变量，可以将递归模拟为迭代。注意，递归和迭代通常是等价的;其中一种几乎总是可以转化为另一种。尾递归函数很容易转化为迭代函数。只需要将累加器变量设置为局部变量，并迭代而不是递归。下面是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;
}

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

堆栈和递归消除文章抓住了将堆栈框架外部化到堆上的思想，但没有提供直接和可重复的转换方法。下面是一个。

在转换为迭代代码时，必须意识到递归调用可能发生在任意深度的代码块中。它不仅是参数，而且是返回到仍然要执行的逻辑的点，以及参与后续条件的变量的状态，这很重要。下面是一种转换为迭代代码的非常简单的方法。

考虑下面的递归代码:

struct tnode
{
    tnode(int n) : data(n), left(0), right(0) {}
    tnode *left, *right;
    int data;
};

void insertnode_recur(tnode *node, int num)
{
    if(node->data <= num)
    {
        if(node->right == NULL)
            node->right = new tnode(num);
        else
            insertnode(node->right, num);
    }
    else
    {
        if(node->left == NULL)
            node->left = new tnode(num);
        else
            insertnode(node->left, num);
    }    
}

迭代代码:

// Identify the stack variables that need to be preserved across stack 
// invocations, that is, across iterations and wrap them in an object
struct stackitem 
{ 
    stackitem(tnode *t, int n) : node(t), num(n), ra(0) {}
    tnode *node; int num;
    int ra; //to point of return
};

void insertnode_iter(tnode *node, int num) 
{
    vector<stackitem> v;
    //pushing a stackitem is equivalent to making a recursive call.
    v.push_back(stackitem(node, num));

    while(v.size()) 
    {
        // taking a modifiable reference to the stack item makes prepending 
        // 'si.' to auto variables in recursive logic suffice
        // e.g., instead of num, replace with si.num.
        stackitem &si = v.back(); 
        switch(si.ra)
        {
        // this jump simulates resuming execution after return from recursive 
        // call 
            case 1: goto ra1;
            case 2: goto ra2;
            default: break;
        } 

        if(si.node->data <= si.num)
        {
            if(si.node->right == NULL)
                si.node->right = new tnode(si.num);
            else
            {
                // replace a recursive call with below statements
                // (a) save return point, 
                // (b) push stack item with new stackitem, 
                // (c) continue statement to make loop pick up and start 
                //    processing new stack item, 
                // (d) a return point label
                // (e) optional semi-colon, if resume point is an end 
                // of a block.

                si.ra=1;
                v.push_back(stackitem(si.node->right, si.num));
                continue; 
ra1:            ;         
            }
        }
        else
        {
            if(si.node->left == NULL)
                si.node->left = new tnode(si.num);
            else
            {
                si.ra=2;                
                v.push_back(stackitem(si.node->left, si.num));
                continue;
ra2:            ;
            }
        }

        v.pop_back();
    }
}

请注意，代码的结构仍然保持忠于递归逻辑，并且修改是最小的，从而减少了错误的数量。为了便于比较，我用++和——标记了更改。除了v.push_back之外，大多数新插入的块对于任何转换的迭代逻辑都是通用的

void insertnode_iter(tnode *node, int num) 
{

+++++++++++++++++++++++++

    vector<stackitem> v;
    v.push_back(stackitem(node, num));

    while(v.size())
    {
        stackitem &si = v.back(); 
        switch(si.ra)
        {
            case 1: goto ra1;
            case 2: goto ra2;
            default: break;
        } 

------------------------

        if(si.node->data <= si.num)
        {
            if(si.node->right == NULL)
                si.node->right = new tnode(si.num);
            else
            {

+++++++++++++++++++++++++

                si.ra=1;
                v.push_back(stackitem(si.node->right, si.num));
                continue; 
ra1:            ;    

-------------------------

            }
        }
        else
        {
            if(si.node->left == NULL)
                si.node->left = new tnode(si.num);
            else
            {

+++++++++++++++++++++++++

                si.ra=2;                
                v.push_back(stackitem(si.node->left, si.num));
                continue;
ra2:            ;

-------------------------

            }
        }

+++++++++++++++++++++++++

        v.pop_back();
    }

-------------------------

}

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

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