时间戳

首页 > 解决方案 > 比较递归斐波那契与递归阶乘

java - 比较递归斐波那契与递归阶乘

问题描述

这是Sedgewick 和 Wayne的《计算机科学跨学科方法》一书中的练习 2.3.2 ：

编写一个以整数 n 作为参数并返回 ln(n!) 的递归函数。

我用Java写了一个递归方法如下：

public static double lnFactorial(int n)
{
    if (n == 1) return 0;
    return Math.log(n) + lnFactorial(n-1);
}

它在 n 高达大约 10000 时运行得非常快。但是，用于计算第 n 个斐波那契数的看起来相同的递归方法（如下）需要永远计算第 50 个斐波那契数。

public static  long fibonacci(int n)
{
    if (n == 1) return 1;
    if (n == 2) return 1;
    return fibonacci(n-1)+fibonacci(n-2);
}

为什么会有如此巨大的差异？是不是因为斐波那契的递归方法在每次迭代中都会调用自己两次？我仍然无法理解其中的区别！

标签： javarecursionfibonaccifactorial

解决方案

第一种方法递归调用自己一次，因此复杂度为O(n)。第二种方法递归调用自身两次，因此每个递归深度调用的数量加倍，这使得方法O(2 n )。

O(n)和O(2 n )之间的差异是巨大的，这使得第二种方法更慢。

使用第二种方法计算第 50 个数字需要2 50 = 1125899906842624 次递归调用。使用第一种方法只需要50次递归调用。（注意：这些数字不一定准确。我只是添加它们来说明线性和指数方法的大小。）

这里要理解的重要一点是，第二种方法多次计算相同n s 的斐波那契数。查看使用n - 1和n - 2递归调用自身的初始调用。当您使用n-1查看调用时，您会看到它使用n-2和n-3调用自身。你注意到问题了吗？该方法已经用n - 2调用了两次。当你用n - 2查看第一次调用时，它甚至已经用n - 3调用了自己两次。随着递归深度的增加，这种情况会变得越来越糟。

请注意，第一种方法不会以任何相同的值调用自身两次。

推荐阅读