在我多年的编程生涯中，我经常使用递归来解决简单的问题，但我完全意识到，有时由于内存/速度问题，您需要迭代。
所以，在很久以前的某个时候，我去尝试寻找是否存在任何“模式”或教科书上的方法来将常见的递归方法转换为迭代，但一无所获。至少我想不起有什么帮助。
有一般的规则吗? 有“模式”吗?
当前回答
在谷歌中搜索“延续传递样式”。有一个转换为尾部递归样式的一般过程;还有一个将尾部递归函数转换为循环的通用过程。
其他回答
努力使你的递归调用尾部递归(递归的最后一个语句是递归调用)。一旦你有了它，将它转换为迭代通常是相当容易的。
这个链接提供了一些解释，并提出了保持“位置”的想法，以便能够在几个递归调用之间到达确切的位置:
但是，所有这些示例都描述了递归调用进行固定次数的场景。当你遇到以下情况时，事情就变得棘手了:
function rec(...) {
for/while loop {
var x = rec(...)
// make a side effect involving return value x
}
}
一般来说，通过简单地使用存储变量，可以将递归模拟为迭代。注意，递归和迭代通常是等价的;其中一种几乎总是可以转化为另一种。尾递归函数很容易转化为迭代函数。只需要将累加器变量设置为局部变量，并迭代而不是递归。下面是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;
}
据我所知，我可能在代码中犯了一个错误，但想法是存在的。
在谷歌中搜索“延续传递样式”。有一个转换为尾部递归样式的一般过程;还有一个将尾部递归函数转换为循环的通用过程。
一个被关闭为这个问题的副本的问题有一个非常特定的数据结构:
节点结构如下:
typedef struct {
int32_t type;
int32_t valueint;
double valuedouble;
struct cNODE *next;
struct cNODE *prev;
struct cNODE *child;
} cNODE;
递归删除函数如下所示:
void cNODE_Delete(cNODE *c) {
cNODE*next;
while (c) {
next=c->next;
if (c->child) {
cNODE_Delete(c->child)
}
free(c);
c=next;
}
}
一般来说，对于多次(甚至一次)调用自身的递归函数，避免使用堆栈并不总是可能的。然而，对于这种特殊的结构，这是可能的。其思想是将所有节点平展为单个列表。这是通过将当前节点的子节点放在顶部行列表的末尾来实现的。
void cNODE_Delete (cNODE *c) {
cNODE *tmp, *last = c;
while (c) {
while (last->next) {
last = last->next; /* find last */
}
if ((tmp = c->child)) {
c->child = NULL; /* append child to last */
last->next = tmp;
tmp->prev = last;
}
tmp = c->next; /* remove current */
free(c);
c = tmp;
}
}
这种技术可以应用于任何可以简化为具有确定性拓扑顺序的DAG的数据链接结构。当前节点子节点被重新排列，以便最后一个子节点采用所有其他子节点。然后可以删除当前节点，然后遍历可以迭代到剩余的子节点。
