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

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

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

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

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

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

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

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

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

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迭代程序。

祝你一切顺利!

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

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