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

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

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

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

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

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

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

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

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

通常避免栈溢出的技术是递归函数，称为蹦床技术，被Java开发人员广泛采用。

然而，对于c#来说，这里有一个小的助手方法，可以将递归函数转换为迭代函数，而不需要改变逻辑或使代码难以理解。c#是一门很好的语言，用它可以做很多神奇的事情。

它的工作原理是用一个辅助方法来包装方法的各个部分。例如下面的递归函数:

int Sum(int index, int[] array)
{
 //This is the termination condition
 if (int >= array.Length)
 //This is the returning value when termination condition is true
 return 0;

//This is the recursive call
 var sumofrest = Sum(index+1, array);

//This is the work to do with the current item and the
 //result of recursive call
 return array[index]+sumofrest;
}

变成:

int Sum(int[] ar)
{
 return RecursionHelper<int>.CreateSingular(i => i >= ar.Length, i => 0)
 .RecursiveCall((i, rv) => i + 1)
 .Do((i, rv) => ar[i] + rv)
 .Execute(0);
}

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

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