在我多年的编程生涯中，我经常使用递归来解决简单的问题，但我完全意识到，有时由于内存/速度问题，您需要迭代。
所以，在很久以前的某个时候，我去尝试寻找是否存在任何“模式”或教科书上的方法来将常见的递归方法转换为迭代，但一无所获。至少我想不起有什么帮助。
有一般的规则吗? 有“模式”吗?
当前回答
实际上，最常见的方法是保留自己的堆栈。下面是一个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;
}
}
显然，这个例子没有检查堆栈边界……实际上，你可以根据最坏的情况来确定堆栈的大小。但你懂的。
其他回答
要寻找的一种模式是函数末尾的递归调用(所谓的尾部递归)。这很容易用一段时间来代替。例如，函数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语言的递归快速排序函数:
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);
}
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”返回一个值，它会检查堆栈，看它是否有任何条目;如果是，则更新堆栈顶部帧中的返回值。关于这个的例子，你可以看看另一个同样方法的递归到迭代转换的例子。
结论
像这样将递归函数转换为迭代函数的方法，本质上也是“递归的”。而不是将流程堆栈用于实际的函数调用，取而代之的是另一个通过编程实现的堆栈。
得到了什么?也许在速度上有一些微不足道的改进。或者，它可以作为一种绕过某些编译器和/或执行环境施加的堆栈限制的方法(堆栈指针击中保护页面)。在某些情况下，可以减少推送到堆栈上的数据量。通过模仿递归实现自动得到的东西，所获得的收益是否抵消了代码中引入的复杂性?
在排序算法的情况下，找到一种方法来实现这个特定的堆栈可能是具有挑战性的，加上有很多迭代排序算法可用得更快。据说任何递归算法都可以迭代地实现。确定……但是有些算法如果没有修改到不再是同一种算法的程度，就不能很好地转换。
仅仅为了转换递归算法而转换递归算法可能不是一个好主意。无论如何，无论如何，上面的方法是一种通用的转换方式，应该适用于任何东西。
如果您发现确实需要递归函数的迭代版本，并且不使用自己的内存消耗堆栈，那么最好的方法可能是放弃代码并使用学术文章中的描述编写自己的代码，或者在纸上完成它，然后从头开始编码，或者其他基础方法。
另一个使用堆栈将递归函数转换为迭代函数的简单而完整的示例。
#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;
}
