递归斐波那契与递归阶乘的比较

Question

这是 Sedgewick 和 Wayne 合着的 Computer Science An Interdisciplinary Approach 一书中的练习 2.3.2：

编写一个递归函数，将整数 n 作为参数，returns 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);
}

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

Answer 1

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

O(n) 和 O(2ⁿ) 之间的区别是巨大的，这使得第二种方法变慢了。

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

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

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

Answer 2

您的斐波那契方法的时间复杂度为 O(2ⁿ)（参见 this 解释），而您的阶乘方法的时间复杂度为 O(n)。

例子理解时间复杂度：

想象一个有 100 名学生的 class 房间，您在其中将笔交给了一个人。现在，你想要那支笔。下面是一些找笔的方法和O顺序是什么

O(n²)：你去问class的第一个人，他有没有钢笔。另外，你问这个人 class 房间里的其他 99 个人是否有那支笔等等，这就是我们所说的O(n²).

O(n)：去每个学生单独询问是 O(n)。 (source)

编辑：O(n²) 的示例与 O(2ⁿ)。这只是时间复杂度的一个例子。

递归斐波那契与递归阶乘的比较

Comparing recursive Fibonacci with recursive factorial

java

recursion

factorial

fibonacci