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

Question

我一直在阅读人们选择使用堆栈而不是递归的几个地方。这是因为递归被视为一种过时的完成工作的方式，还是两种方法在不同的上下文中同样适用？

Answer 1

不，恰恰相反。递归是表达整类问题的自然方式。如果没有递归，堆栈是一种模拟方法。

例如，请参阅此 question .或者考虑那种标准的递归函数:计算第 n 个斐波那契数。

你会记得 Fibonacci numbers是系列

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

定义为 Fn = Fn-1+Fn-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 编写，则必须管理自己的堆栈以跟踪这些中间结果。