在我多年的编程生涯中,我经常使用递归来解决简单的问题,但我完全意识到,有时由于内存/速度问题,您需要迭代。

所以,在很久以前的某个时候,我去尝试寻找是否存在任何“模式”或教科书上的方法来将常见的递归方法转换为迭代,但一无所获。至少我想不起有什么帮助。

有一般的规则吗? 有“模式”吗?


当前回答

努力使你的递归调用尾部递归(递归的最后一个语句是递归调用)。一旦你有了它,将它转换为迭代通常是相当容易的。

其他回答

要寻找的一种模式是函数末尾的递归调用(所谓的尾部递归)。这很容易用一段时间来代替。例如,函数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;
     }
}

这消除了第二次递归调用。

在谷歌中搜索“延续传递样式”。有一个转换为尾部递归样式的一般过程;还有一个将尾部递归函数转换为循环的通用过程。

通常,通过将通常传递给递归函数的参数推入堆栈,我将递归算法替换为迭代算法。事实上,您正在用自己的程序堆栈替换程序堆栈。

var stack = [];
stack.push(firstObject);

// while not empty
while (stack.length) {

    // Pop off end of stack.
    obj = stack.pop();

    // Do stuff.
    // Push other objects on the stack as needed.
    ...

}

注意:如果你在里面有多个递归调用,并且你想要保留调用的顺序,你必须以相反的顺序将它们添加到堆栈:

foo(first);
foo(second);

必须由

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

编辑:文章堆栈和递归消除(或文章备份链接)详细介绍了这个主题。

一个系统如何接受任何递归函数并使用堆栈执行它的粗略描述:

这是为了在没有细节的情况下展示想法。考虑这个函数,它将打印出图的节点:

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。

为了执行代码,系统运行指令。当遇到函数调用时,系统将需要的信息推回到原来的位置,运行函数代码,当函数完成时,弹出关于需要继续执行的位置的信息。

实际上,最常见的方法是保留自己的堆栈。下面是一个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;
    }
}

显然,这个例子没有检查堆栈边界……实际上,你可以根据最坏的情况来确定堆栈的大小。但你懂的。