与使用堆栈相比,递归通常被认为是一种过时的遍历方法吗？

Question

我一直在读几个人们选择使用Stack而不是递归的地方.这是因为递归被认为是完成工作的过时方式,或者这两种方法在不同的环境中同样适用吗？

Answer 1

不,恰恰相反.递归是表达一类问题的自然方式.如果您没有递归,则堆栈是一种模拟该方法的方法.

例如,请参阅此问题.或者考虑一下标准的递归函数:计算第n个Fibonacci数.

你会记得Fibonacci数字是系列

0,1,1,2,3,5,8,13, ...

定义使得F _n = F _n-1 + F _n-2.

这可以写为递归定义

基本情况:
F(0)= 0
F(1)= 1
递归步骤:
F(n)= F(n-1)+ F(n-2)

所以,你有F(0)= 0,F(1)= 1,F(2)= F(0)+ F(1)= 1,依此类推.

计算这个的简单程序(在C中只是为了咧嘴)是:

int fib(int n) {
    /* we'll ignore possible negative arguments, see Wikipedia */
    switch(n) {
       case 0: return 0; break;
       case 1: return 1; break;
       default: return fib(n-1)+fib(n-2); break;
    }
}

请注意该程序与原始定义的对应程度如何？

问题是,C管理调用堆栈中的所有中间结果.有些语言没有被定义为这样做(我唯一可以想到的是旧的FORTRAN,但我确信还有其他语言).如果您使用汇编程序或旧FORTRAN编写,则必须管理自己的堆栈以跟踪这些中间结果.

Answer 2

迭代通常比递归更快/更少开销.通过递归,我们隐式地使用机器的堆栈作为我们的堆栈 - 我们"免费"获得 - 但我们支付昂贵的函数调用(以及随之而来的机器堆栈管理)的成本.

但是递归函数通常更直观地编写和读取.

通常,可以使用递归编写函数,将其保留直至成为瓶颈,然后将其替换为使用显式堆栈的迭代函数.

Answer 3

更新为包括鱼嘴修正.

使用Stack是消除递归的标准技术

另请参阅:什么是尾递归？

Tail-Recursion的一个例子(可以使用迭代删除):

public class TailTest
{   
    public static void Main()
    {       
        TailTest f = new TailTest();
        f.DoTail(0);
    }

    public void DoTail(int n)
    {       
        int v = n + 1;      
        System.Console.WriteLine(v);    

        DoTail(v);   // Tail-Recursive call
    }
}