不论是在算法还是在编程语言的教材中，都可能会以斐波那契数列为例，或说明其算法上的特点——主要是递归，或说明如何运用某种编程语言编写相应函数。

本文是一篇关于“斐波那契数列”的专题文章，目的是让学习《数据结构》这门课程的同学对此问题有完整的理解。

1. 斐波那契数列

斐波那契数列于公元1150年被印度数学家发现，而后意大利人斐波那契（Leonardo Fibonacci, 1175－1250）在描述兔子生长的数目时用上了这数列：

• 第一个月初有一对刚诞生的兔子；
• 第二个月之后（第三个月初）它们可以生育；
• 每月每对可生育的兔子会诞生下一对新兔子；
• 兔子永不死。

假设在 $n$ 月有兔子总共 $a$ 对， $n+1$ 月总共有 $b$ 对。在 $n+2$ 月必定总共有 $a+b$ 对：因为在 $n+2$ 月的时候，前一月（ $n+1$ 月）的 $b$ 对兔子可以存留至第 $n+2$ 月（在当月属于新诞生的兔子尚不能生育）。而新生育出的兔子对数等于所有在 $n$ 月就已存在的 $a$ 对。

斐波纳契数是帕斯卡三角形的每一条红色对角线上数字的和。

用递归方式定义斐波那契数列：
$$fib(n)=\{\begin{array}{ll}1& (n=0或n=1)\\ fib(n-1)+fib(n-2)& (n>1)\end{array}$$

1.1 时间复杂度

根据以上表达式，写出相应的算法描述

long fib(long n){if(n == 1 || n == 2) return 1;else return fib(n-1) + fib(n-2);
}

下面分析上述算法描述的时间复杂度。

假设计算 fib(n) 的时间是 $T(n)$ ，先花费 $T(n-1)$ 时间计算 fib(n-1) ；再花费 $T(n-2)$ 时间计算 fib(n-2) ；最后用 1 个时间单元将二者相加。由此写出 $T(n)$ 的递推式：
$$T(n)=\{\begin{array}{ll}1& (n\le 1)\\ T(n-1)+T(n-2)+1& (\text{others})\end{array}$$
令 $S(n)=\frac{T(n)+1}{2}$ ，则上式可以写成：
$$S(n)=\{\begin{array}{ll}1& (n\le 1)\\ S(n-1)+S(n-2)& (\text{others})\end{array}$$
将此式与斐波那契数列的函数式对比：
$$fib(n)=\{\begin{array}{ll}1& (n=0或n=1)\\ fib(n-1)+fib(n-2)& (n>1)\end{array}$$
$S(n)$ 与 $fib(n)$ 在形式上基本一样，只是起始项不同，有归纳可得：
$$\begin{array}{rl}S(0)& =1=fib(1)\\ S(1)& =1=fib(2)\\ & ⋮\\ S(n)& =fib(n-1)\end{array}$$
根据 $fib(n)$ 可以解得（求解过程参见本节拓展内容）：
$$fib(n)=\frac{1}{\sqrt{5}}\left[{\left(\frac{1+\sqrt{5}}{2}\right)}^n-{\left(\frac{1-\sqrt{5}}{2}\right)}^n\right],(n=0,1,2,\cdots )$$
令 $\phi =\frac{1+\sqrt{5}}{2}$ （黄金比例），则 $fib(n)=\frac{1}{\sqrt{5}}[{\phi }^n-(1-\phi {)}^n]$ 。

所以：
$$\begin{array}{rl}& S(n)=fib(n+1)=\frac{1}{\sqrt{5}}[{\phi }^{(n+1)}-(1-\phi {)}^{(n+1)}]\\ & \therefore T(n)=2S(n)-1=2\cdot fib(n+1)-1=O({\phi }^{n+1})\end{array}$$
由此可知，以递归方式实现的斐波那契数列的时间复杂度为指数级，不是一个有价值的算法。其原因在于违反了设计递归算法的基本原则中的合成效益法则。根据 $fib(n)$ 的递归函数，追踪调用过程，当第一次调用 $fib(n-1)$ 时，$fib(n-2)$ 实际上已经计算了，在后面还要再计算 $fib(n-2)$ 。即同一个实例，在递归过程中，重复计算，从而导致运行时间暴增。

1.2 计算斐波那契数列的通项

设 $F_k$ 为斐波那契数列中的第 $k$ 项，则：

$$F_{k+2}=F_{k+1}+F_k,(k=0,1,2,\cdots )\text{\hspace{1em}(1)}$$
根据斐波那契数列的特点，初始条件是：$F_0=0,F_1=1$ 。

将（1）式写成：

$$\{\begin{array}{l}{F}_{k+2}=F_{k+1}+F_k\\ F_{k+1}=F_{k+1}\end{array}$$
以矩阵方式表示为：

$$\left[\begin{array}{c}{F}_{k+2}\\ F_{k+1}\end{array}\right]=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\left[\begin{array}{c}{F}_{k+1}\\ F_k\end{array}\right]\text{\hspace{1em}(2)}$$

1.2.1 第一种方法

令 $u_k=\left[\begin{array}{c}{F}_{k+1}\\ F_k\end{array}\right]$ ，由（2）式得到：

$$u_{k+1}={Au}_k,(k=0,1,\cdots )\text{\hspace{1em}(3)}$$
其中，$A=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$ ，初始条件 $u_0=\left[\begin{array}{c}{F}_1\\ F_0\end{array}\right]=\left[\begin{array}{c}1\\ 0\end{array}\right]$ 。

（3）式查分方程（参见《机器学习数学基础》第 3 章 3.2.2，齐伟，电子工业出版社）。

又因为：
$$u_k={Au}_{k-1}=A({Au}_{k-2})=A^2{u}_{k-2}=\cdots =A^k{u}_0\text{\hspace{1em}(4)}$$
所以，只要计算出 $A^k$ ，然后将它与初始条件 $u_0$ 相乘，即得到 $u_k$ 。

对于矩阵 $A=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$ ，其特征多项式：

$$|A-\lambda I|=\left|\begin{array}{cc}1-\lambda & 1\\ 1& -\lambda \end{array}\right|={\lambda }^2-\lambda -1$$
根据特征方程：$|A-\lambda I|=0$ ，得：

$${\lambda }^2-\lambda -1=0\text{\hspace{1em}(5)}$$
解得：

$$\{\begin{array}{l}{\lambda }_1=\frac{1+\sqrt{5}}{2}\\ {\lambda }_2=\frac{1-\sqrt{5}}{2}\end{array}\text{\hspace{1em}(6)}$$
显然，${\lambda }_1+{\lambda }_2=1,{\lambda }_1{\lambda }_2=-1$ 。

再根据 $Ax=\lambda x$ 计算（6）中每个特征值所对应的特征向量。

当 $\lambda ={\lambda }_1$ 时，设特征向量为 $\left[\begin{array}{c}{x}_1\\ y_1\end{array}\right]$ ，则：

$$\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]\left[\begin{array}{c}{x}_1\\ y_1\end{array}\right]={\lambda }_1\left[\begin{array}{c}{x}_1\\ y_1\end{array}\right]$$
可得：$\left[\begin{array}{c}{x}_1\\ y_1\end{array}\right]=\left[\begin{array}{c}{\lambda }_1\\ 1\end{array}\right]$ 是满足条件的一个向量，即特征向量 $x_1=\left[\begin{array}{c}{\lambda }_1\\ 1\end{array}\right]$ （将 $\left[\begin{array}{c}{\lambda }_1\\ 1\end{array}\right]$ 代入到上式，并利用（5）式，上式成立，即说明 $\left[\begin{array}{c}{\lambda }_1\\ 1\end{array}\right]$ 是一个基向量）。

同理，求得另外一个特征值 ${\lambda }_2$ 所对应的特征向量 $x_2=\left[\begin{array}{c}{\lambda }_2\\ 1\end{array}\right]$ 。

$$\{\begin{array}{l}{x}_1=\left[\begin{array}{c}{\lambda }_1\\ 1\end{array}\right]\\ x_2=\left[\begin{array}{c}{\lambda }_2\\ 1\end{array}\right]\end{array}\text{\hspace{1em}(7)}$$
很显然，特征向量 $x_1$ 和 $x_2$ 线性无关，则矩阵 $A=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$ 可以对角化（参阅《机器学习数学基础》第3章3.3.3节）。

设 $A={CDC}^{-1}$ ，其中 $C$ 的列向量即为 $A$ 的特征向量，$D$ 为特征向量构成的对角矩阵（参阅《机器学习数学基础》第3章3.3.3节（3.3.10）式和（3.3.11）式）。

因为：$A^k=C{D}^k{C}^{-1}$

于是（4）式可以转化为：

$$u_k=C{D}^k{C}^{-1}{u}_0\text{\hspace{1em}(8)}$$
由于 $u_0$ 是一个列向量，则 $C^{-1}{u}_0$ 结果也是列向量，故令 $c=C^{-1}{u}_0$ ，（8）式变换为：

$$u_k=C{D}^{k}c\text{\hspace{1em}(9)}$$
若用一般化的式子表示，$C=\left[\begin{array}{cc}{x}_1& \cdots x_n\end{array}\right]$ （由 $A$ 的 $n$ 个特征向量组成），$D^k=\left[\begin{array}{ccc}{\lambda }_1^k& \cdots & 0\\ 0& \ddots & 0\\ 0& \cdots & {\lambda }_n^k\end{array}\right]$ ，代入（9）式：

$$\begin{array}{rl}{u}_k& =\left[\begin{array}{cc}{x}_1& \cdots x_n\end{array}\right]\left[\begin{array}{ccc}{\lambda }_1^k& \cdots & 0\\ 0& \ddots & 0\\ 0& \cdots & {\lambda }_n^k\end{array}\right]\left[\begin{array}{c}{c}_1\\ ⋮\\ c_n\end{array}\right]\\ & =\left[\begin{array}{ccc}{\lambda }_1^k{x}_1& \cdots & {\lambda }_n^k{x}_n\end{array}\right]\left[\begin{array}{c}{c}_1\\ ⋮\\ c_n\end{array}\right]\\ & =c_1{\lambda }_1^k{x}_1+\cdots +c_n{\lambda }_n^k{x}_n\end{array}$$
即：

$$u_k=c_1{\lambda }_1^k{x}_1+\cdots +c_n{\lambda }_n^k{x}_n\text{\hspace{1em}(10)}$$
若 $k=0$ ，则（9）式即为：$u_0={CD}^{0}c=CIc=Cc$ ，从而得到（10）式中的系数 $c_1,\cdots ,c_n$ 。（10）式即为差分方程的通解（《机器学习数学基础》第3章3.2.2节，给出了差分方程通解的另外一种计算方法，在该方法中没有使用对矩阵 $A$ 可对角化的假设）。

现在将 $A=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$ 的特征向量（7）和特征值（6）式分别代入（10）式，即得到（3）差分方程的通解：

$$u_k=c_1{\lambda }_1^k{x}_1+c_2{\lambda }_2^k{x}_2\text{\hspace{1em}(11)}$$
当 $k=0$ 时，$u_0=\left[\begin{array}{c}1\\ 0\end{array}\right]$ ，${\lambda }_1^0={\lambda }_2^0=1$，代入（11）式：

$$\left[\begin{array}{c}1\\ 0\end{array}\right]=c_1{x}_1+c_2{x}_2=c_1\left[\begin{array}{c}\frac{1+\sqrt{5}}{2}\\ 1\end{array}\right]+c_2\left[\begin{array}{c}\frac{1-\sqrt{5}}{2}\\ 1\end{array}\right]$$
解得：

$$\{\begin{array}{l}{c}_1=\frac{1}{\sqrt{5}}\\ c_2=-\frac{1}{\sqrt{5}}\end{array}$$
代入（11），同时将特征值和特征向量也代入，得：

$$\begin{array}{rl}{u}_k& =\frac{1}{\sqrt{5}}{\left(\frac{1+\sqrt{5}}{2}\right)}^k\left[\begin{array}{c}\frac{1+\sqrt{5}}{2}\\ 1\end{array}\right]-\frac{1}{\sqrt{5}}{\left(\frac{1-\sqrt{5}}{2}\right)}^k\left[\begin{array}{c}\frac{1-\sqrt{5}}{2}\\ 1\end{array}\right]\\ & =\frac{1}{\sqrt{5}}\left[\begin{array}{c}{\left(\frac{1+\sqrt{5}}{2}\right)}^{k+1}\\ {\left(\frac{1+\sqrt{5}}{2}\right)}^k\end{array}\right]-\frac{1}{\sqrt{5}}\left[\begin{array}{c}{\left(\frac{1-\sqrt{5}}{2}\right)}^{k+1}\\ {\left(\frac{1-\sqrt{5}}{2}\right)}^k\end{array}\right]\\ & =\frac{1}{\sqrt{5}}\left[\begin{array}{c}{\left(\frac{1+\sqrt{5}}{2}\right)}^{k+1}-{\left(\frac{1-\sqrt{5}}{2}\right)}^{k+1}\\ {\left(\frac{1+\sqrt{5}}{2}\right)}^k-{\left(\frac{1-\sqrt{5}}{2}\right)}^k\end{array}\right]\end{array}$$
在（3）式中假设 $u_k=\left[\begin{array}{c}{F}_{k+1}\\ F_k\end{array}\right]$ ，对比上式，则：

$$F_k=\frac{1}{\sqrt{5}}\left[{\left(\frac{1+\sqrt{5}}{2}\right)}^k-{\left(\frac{1-\sqrt{5}}{2}\right)}^k\right],(k=0,1,2,\cdots )\text{\hspace{1em}(12)}$$
这样就得到了斐波那契数列通项表达式。

3.2 第二种方法

由于 $A=\left[\begin{array}{cc}1& 1\\ 1& 0\end{array}\right]$ 可对角化，根据 $A={CDC}^{-1}\Rightarrow A^k=C{D}^k{C}^{-1}$ 得：

$$A^k=C\left[\begin{array}{cc}{\lambda }_1^k& 0\\ 0& {\lambda }_2^k\end{array}\right]C^{-1}\text{\hspace{1em}(13)}$$
其中 $C=\left[\begin{array}{cc}{\lambda }_1& {\lambda }_2\\ 1& 1\end{array}\right]$ （ $C$ 由特征向量 $x_1$、$x_2$ 构成），则 $C^{-1}=\left[\begin{array}{cc}\frac{1}{{\lambda }_1-{\lambda }_2}& \frac{{\lambda }_2}{{\lambda }_2-{\lambda }_1}\\ \frac{1}{{\lambda }_2-{\lambda }_1}& \frac{{\lambda }_1}{{\lambda }_1-{\lambda }_2}\end{array}\right]=\frac{1}{{\lambda }_1-{\lambda }_2}\left[\begin{array}{cc}1& -{\lambda }_2\\ -1& {\lambda }_1\end{array}\right]$ 。

由（4）式可得：

$$\left[\begin{array}{c}{F}_{k+1}\\ F_k\end{array}\right]=A^k\left[\begin{array}{c}1\\ 0\end{array}\right]$$
将（13）代入上式，可得：

$$\begin{array}{rl}\left[\begin{array}{c}{F}_{k+1}\\ F_k\end{array}\right]& =C\left[\begin{array}{cc}{\lambda }_1^k& 0\\ 0& {\lambda }_2^k\end{array}\right]C^{-1}\left[\begin{array}{c}1\\ 0\end{array}\right]\\ & =\frac{1}{{\lambda }_1-{\lambda }_2}\left[\begin{array}{cc}{\lambda }_1& {\lambda }_2\\ 1& 1\end{array}\right]\left[\begin{array}{cc}{\lambda }_1^k& 0\\ 0& {\lambda }_2^k\end{array}\right]\left[\begin{array}{cc}1& -{\lambda }_2\\ -1& {\lambda }_1\end{array}\right]\left[\begin{array}{c}1\\ 0\end{array}\right]\\ & =\frac{1}{{\lambda }_1-{\lambda }_2}\left[\begin{array}{c}{\lambda }_1^{k+1}-{\lambda }_1^{k+1}\\ {\lambda }_1^k-{\lambda }_2^k\end{array}\right]\end{array}$$
所以，通项表达式：

$$\begin{array}{rl}{F}_k& =\frac{{\lambda }_1^k-{\lambda }_2^k}{{\lambda }_1-{\lambda }_2}=\frac{{\left(\frac{1+\sqrt{5}}{2}\right)}^k-{\left(\frac{1-\sqrt{5}}{2}\right)}^k}{\left(\frac{1+\sqrt{5}}{2}\right)-\left(\frac{1-\sqrt{5}}{2}\right)}\\ & =\frac{1}{\sqrt{5}}\left[{\left(\frac{1+\sqrt{5}}{2}\right)}^k-{\left(\frac{1-\sqrt{5}}{2}\right)}^k\right],(k=0,1,2,\cdots )\end{array}$$

与（12）式一样的结果。