3

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

4

5 回答 5

15

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

例如，参见这个问题。或者考虑一种标准递归函数：计算第n个斐波那契数。

你会记得斐波那契数列

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

于 2009-04-28T01:34:31.893 回答
10

迭代通常比递归更快/开销更少。通过递归，我们隐式地使用机器的堆栈作为我们的堆栈——我们“免费”获得它——但我们付出了昂贵的函数调用（以及随之而来的机器堆栈管理）的成本。

但是递归函数通常更易于书写和阅读。

通常，可以使用递归来编写函数，直到它成为瓶颈，然后用使用显式堆栈的迭代函数替换它。

于 2009-04-28T01:36:21.310 回答
6

更新以包括鱼唇的更正。

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

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

尾递归的一个例子（可以使用迭代删除）：

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
    }
}
于 2009-04-28T01:35:05.760 回答
4

如果您处于尾调用增长堆栈（未应用尾调用优化（TCO））的编程语言/环境中，那么最好避免深度递归，并且可能使用堆栈数据结构的迭代解决方案是首选。

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

（这有点过于宽泛，但总的来说，我绝不会称递归“过时”。）

于 2009-04-28T01:37:11.340 回答
3

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

如果问题是递归的，我完全推荐你的递归解决方案。

此外，您最终可能会引入一些意料之外的错误，试图强制执行迭代/堆叠解决方案。

于 2010-04-16T15:56:30.960 回答