斐波那契数列是指如下整数序列：0, 1, 1, 2, 3, 5, 8, 13…。所谓的斐波那契数，就是前两个斐波那契数之和，其中前两个数固定为 0 和 1。
第 n 个斐波那契数可以递归地表示为：
> F(n) = F(n-1) + F(n-2)
>
> 基础值：F(0) = 0 且 F(1) = 1
在继续阅读之前，请确保你已经熟悉了 斐波那契数列程序 中讨论的递归方法。
递归斐波那契程序的分析：
我们知道，斐波那契数列的递归方程是 = T(n-1) + T(n-2) + O(1)。
这意味着，计算 fib(n) 所花费的时间，等于计算 fib(n-1) 和 fib(n-2) 所花费的时间之和。这还包括了执行加法运算所需的常数时间。在求解上述递归方程时，我们得到斐波那契数列时间复杂度的上界为 O(2n)，但这并不是紧上界（Tight Upper Bound）。事实上，斐波那契数列在数学上可以表示为一个线性递归函数，我们可以利用这一点来找到紧上界。现在斐波那契数列定义为 F(n) = F(n-1) + F(n-2)
- 该函数的特征方程将是 x2 = x2-x-1 = 0。
- 使用二次公式求解，我们可以得到根为 x = (1+√5)/2 和 x = (1-√5)/2 。
- 现在我们知道，线性递归函数的解由 F(n) 给出
F(n) = (α1)n + (α2)n，其中 α1 和 α2 是特征方程的根。因此，对于我们的斐波那契函数 F(n) = F(n-1) + F(n-2)，解将是：
****F(n) = ( (1+√5)/2 )********n******** + ( (1-√5)/2 )********n ******** ****
显然，T(n) 和 F(n) 在渐近意义上是相同的，因为两个函数代表的是同一事物。因此可以说：
T(n) = O( ( (1+√5)/2 )n + ( (1-√5)/2 )n )，或者我们可以写出下面的式子（利用 大O表示法 的性质，我们可以忽略低阶项）。
- T(n) = O ( (1+√5)/2 )n
- T(n) = O(1.6180)n，这就是斐波那契数列的紧上界。
> 趣味冷知识： 1.6180 也被称为黄金比例。你可以在这里阅读更多关于黄金比例的内容：数学中的黄金比例