在我多年的编程生涯中,我经常使用递归来解决简单的问题,但我完全意识到,有时由于内存/速度问题,您需要迭代。
所以,在很久以前的某个时候,我去尝试寻找是否存在任何“模式”或教科书上的方法来将常见的递归方法转换为迭代,但一无所获。至少我想不起有什么帮助。
有一般的规则吗? 有“模式”吗?
在我多年的编程生涯中,我经常使用递归来解决简单的问题,但我完全意识到,有时由于内存/速度问题,您需要迭代。
所以,在很久以前的某个时候,我去尝试寻找是否存在任何“模式”或教科书上的方法来将常见的递归方法转换为迭代,但一无所获。至少我想不起有什么帮助。
有一般的规则吗? 有“模式”吗?
当前回答
实际上,最常见的方法是保留自己的堆栈。下面是一个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;
}
}
显然,这个例子没有检查堆栈边界……实际上,你可以根据最坏的情况来确定堆栈的大小。但你懂的。
其他回答
有一种将递归遍历转换为迭代器的通用方法,即使用连接多个迭代器提供者的惰性迭代器(返回迭代器的lambda表达式)。请参阅我的将递归遍历转换为迭代器。
一个被关闭为这个问题的副本的问题有一个非常特定的数据结构:
节点结构如下:
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的数据链接结构。当前节点子节点被重新排列,以便最后一个子节点采用所有其他子节点。然后可以删除当前节点,然后遍历可以迭代到剩余的子节点。
只是消磨时间……递归函数
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);
}
}
一般来说,通过简单地使用存储变量,可以将递归模拟为迭代。注意,递归和迭代通常是等价的;其中一种几乎总是可以转化为另一种。尾递归函数很容易转化为迭代函数。只需要将累加器变量设置为局部变量,并迭代而不是递归。下面是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;
}
据我所知,我可能在代码中犯了一个错误,但想法是存在的。
一个系统如何接受任何递归函数并使用堆栈执行它的粗略描述:
这是为了在没有细节的情况下展示想法。考虑这个函数,它将打印出图的节点:
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。
为了执行代码,系统运行指令。当遇到函数调用时,系统将需要的信息推回到原来的位置,运行函数代码,当函数完成时,弹出关于需要继续执行的位置的信息。