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

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

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

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

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

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

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

在谷歌中搜索“延续传递样式”。有一个转换为尾部递归样式的一般过程;还有一个将尾部递归函数转换为循环的通用过程。

通常，通过将通常传递给递归函数的参数推入堆栈，我将递归算法替换为迭代算法。事实上，您正在用自己的程序堆栈替换程序堆栈。

var stack = [];
stack.push(firstObject);

// while not empty
while (stack.length) {

    // Pop off end of stack.
    obj = stack.pop();

    // Do stuff.
    // Push other objects on the stack as needed.
    ...

}

注意:如果你在里面有多个递归调用，并且你想要保留调用的顺序，你必须以相反的顺序将它们添加到堆栈:

foo(first);
foo(second);

必须由

stack.push(second);
stack.push(first);

编辑:文章堆栈和递归消除(或文章备份链接)详细介绍了这个主题。

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

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