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

迭代通常比递归更快/开销更小。通过递归,我们隐式地使用机器的堆栈作为我们的堆栈——我们“免费”得到它——但是我们要支付昂贵的函数调用(以及随之而来的机器堆栈管理)的成本。

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

通常,可以使用递归编写一个函数,在它成为瓶颈之前保留它,然后用使用显式堆栈的迭代函数替换它。

不,正好相反。递归是表达一类问题的自然方法。如果没有递归,堆栈就是一种模拟这种情况的方法。

例如,请参见 question . 或者考虑标准递归函数的类型:计算 n -斐波那契数。

你会记得的 Fibonacci numbers 是系列

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语言,仅用于GRIS)是:

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编写,那么您必须管理自己的堆栈以跟踪这些中间结果。

更新的 包括鱼唇矫正。

使用堆栈是消除 recursion

参见: What is 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
    }
}

如果您所处的编程语言/环境中使用的是尾调用增加堆栈(没有应用尾调用优化(TCO)),那么最好避免深度递归,最好使用可能使用堆栈数据结构的迭代解决方案。

另一方面,如果您所处的语言/环境支持使用尾调用进行迭代,或者递归深度总是很小,那么递归通常是一个好的/优雅的解决方案。

(这有点过于宽泛,但总的来说,我决不会称递归为“过时的”。)

不,不,我认为现代开发人员应该在几毫秒内强调可读性和易维护性。

如果问题是递归的,我完全建议您的解决方案是递归的。

此外,您最终可能会引入一些未检查的bug,试图强制执行迭代/堆叠解决方案。