这是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);
}
为什么会有如此巨大的差异？是因为斐波那契的递归方法在每次迭代中调用自己两次吗？我仍然无法理解其中的区别！
第一种方法递归调用自身一次，因此复杂度为O(n(。第二个方法递归地调用自身两次，因此每个递归深度的调用量加倍，这使得方法O(2n(。
O(n( 和O(2n(之间的差异是巨大的，这使得第二种方法的速度较慢。
使用第二种方法计算第 50 个数字需要250= 1125899906842624次递归调用。使用第一种方法只需要50次递归调用。(注意：这些数字不得准确。我刚刚添加了它们来说明线性和指数方法的大小。
这里要了解的重要一点是，第二种方法多次计算相同n的斐波那契数。查看使用 n - 1 和n - 2递归调用自己的初始调用。当您查看带有 n - 1 的调用时，您会看到它使用 n - 2 和n - 3调用自身。你注意到问题了吗？该方法已经被n - 2调用了两次。它甚至已经用 n -3调用了两次，当你查看第一次用n - 2调用时。随着递归深度的增加，这种情况会变得越来越糟。
请注意，第一个方法不会使用任何相同的值调用自身两次。
斐波那契方法的时间复杂度为 O(2 n((请参阅此解释(，而阶乘方法的时间复杂度为O(n(。
了解时间复杂度的示例：
想象一下，一个有100名学生的教室，你把笔交给一个人。现在，你想要那支笔。以下是查找笔和 O 顺序的一些方法。
O(n2(：你去问班上的第一个人，他有没有笔。另外，你问这个人教室里的其他99个人是否有那支笔等等， 这就是我们所说的O(n2(。
O(n(：去单独询问每个学生是O(n(。(来源(
编辑：O(n 2(的示例与O(2n(不同。这只是一个关于时间复杂性意味着什么的例子。