在我多年的编程生涯中，我经常使用递归来解决简单的问题，但我完全意识到，有时由于内存/速度问题，您需要迭代。
所以，在很久以前的某个时候，我去尝试寻找是否存在任何“模式”或教科书上的方法来将常见的递归方法转换为迭代，但一无所获。至少我想不起有什么帮助。
有一般的规则吗? 有“模式”吗?
当前回答
一个被关闭为这个问题的副本的问题有一个非常特定的数据结构:
节点结构如下:
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的数据链接结构。当前节点子节点被重新排列，以便最后一个子节点采用所有其他子节点。然后可以删除当前节点，然后遍历可以迭代到剩余的子节点。
其他回答
努力使你的递归调用尾部递归(递归的最后一个语句是递归调用)。一旦你有了它，将它转换为迭代通常是相当容易的。
这个链接提供了一些解释，并提出了保持“位置”的想法，以便能够在几个递归调用之间到达确切的位置:
但是，所有这些示例都描述了递归调用进行固定次数的场景。当你遇到以下情况时，事情就变得棘手了:
function rec(...) {
for/while loop {
var x = rec(...)
// make a side effect involving return value x
}
}
在谷歌中搜索“延续传递样式”。有一个转换为尾部递归样式的一般过程;还有一个将尾部递归函数转换为循环的通用过程。
即使使用堆栈也不能将递归算法转换为迭代算法。普通的递归是基于函数的递归，如果我们使用堆栈，那么它就变成了基于堆栈的递归。但它仍然是递归。
对于递归算法，空间复杂度为O(N)，时间复杂度为O(N)。 对于迭代算法，空间复杂度为O(1)，时间复杂度为O(N)。
但是如果我们使用堆栈的话复杂度还是一样的。我认为只有尾递归可以转化为迭代。
一个系统如何接受任何递归函数并使用堆栈执行它的粗略描述:
这是为了在没有细节的情况下展示想法。考虑这个函数，它将打印出图的节点:
function show(node)
0. if isleaf(node):
1. print node.name
2. else:
3. show(node.left)
4. show(node)
5. show(node.right)
例如图表: A - B > C - > show(A)将打印B, A, C
函数调用意味着保存本地状态和延续点，以便返回，然后跳转到要调用的函数。
例如，假设show(A)开始运行。函数调用在第3行。显示(B)的意思 -将项目添加到堆栈，意思是“你需要在第2行继续使用本地变量状态node=A” —到第0行，节点为B。
为了执行代码，系统运行指令。当遇到函数调用时，系统将需要的信息推回到原来的位置，运行函数代码，当函数完成时，弹出关于需要继续执行的位置的信息。
