在多年的编程中，我已经使用了很多递归来解决简单的问题，但是我完全意识到有时由于内存/速度问题而需要迭代。

因此，在很久以前的某个时候，我去尝试寻找是否存在将通用递归方法转换为迭代的任何"模式"或者教科书方法，却一无所获。或者至少没有什么我能记住的会有所帮助。

• 有一般规则吗？
• 有没有"模式"？

解决方案

努力进行递归调用Tail Recursion(最后一条语句为递归调用的递归)。一旦有了它，将其转换为迭代通常就很容易了。

在Google上搜索"继续传递样式"。有一个转换为尾部递归样式的通用过程。还有将尾递归函数转换为循环的通用过程。

要寻找的一种模式是在函数末尾进行递归调用(所谓的尾递归)。可以轻松地将其替换一会儿。例如，函数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;
     }
}

这样就消除了第二个递归调用。

好吧，通常，只需使用存储变量，就可以将递归模拟为迭代。注意，递归和迭代通常是等效的。一个几乎总是可以转换为另一个。尾递归函数很容易转换为迭代函数。只需将累加器变量设为局部变量，然后迭代而不是递归即可。这是C ++中的一个示例(如果不使用默认参数，则为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;
}

认识我，我可能在代码中犯了一个错误，但是想法就在那里。

确实，最常用的方法是保留自己的堆栈。这是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;
    }
}

显然，此示例不检查堆栈边界...实际上，我们可以根据给定的left和right值的最坏情况确定堆栈的大小。但是你明白了。

通常，我通过将通常会传递给递归函数的参数推入堆栈，用迭代算法代替递归算法。实际上，我们是用自己的一个替换程序堆栈。

Stack<Object> stack;
stack.push(first_object);
while( !stack.isEmpty() ) {
   // Do something
   my_object = stack.pop();

  // Push other objects on the stack.

}

注意：如果内部有多个递归调用，并且想要保留调用顺序，则必须以相反的顺序将它们添加到堆栈中：

foo(first);
foo(second);

必须替换为

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

编辑：文章堆栈和递归消除(或者文章备份链接)进入了关于此主题的更多详细信息。

我只是对答案提出建议，建议使用一个我认为是正确的解决方案并且具有普遍适用性的显式堆栈。

我的意思是，我们可以使用它来转换迭代函数中的任何递归函数。只需检查在递归调用中保存了哪些值，这些值必须在递归函数中是局部的，然后将这些调用替换为一个循环，即可将它们压入堆栈。当堆栈为空时，递归函数将被终止。

我不能不说每个递归函数都等同于不同数据类型上的迭代函数的证明，这是我大学时代最宝贵的记忆之一。那是一门课程(和教授)，确实使我了解了计算机编程的含义。

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

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

但是，如果我们使用堆栈，那么复杂性就保持不变。我认为只有尾递归可以转换为迭代。