周卫星 陈思 张帆

（中国移动（深圳）有限公司，广东深圳518048）

矩阵乘法在斐波那契数列计算中的应用

周卫星 陈思 张帆

（中国移动（深圳）有限公司，广东深圳518048）

本文介绍了斐波那契数列的一些算法思路，对递归算法、自底向上、比内公式等算法的时间复杂度进行了分析，给出了利用矩阵乘法升维计算降低时间复杂度的方法，对比测试了各算法实现在不同计算量下的执行时间。针对数据溢出，将long数据类型改进为BigInteger的数据类型,给出了大数计算下的执行时间对比。

斐波那契；递归；比内公式；矩阵

1 引言

斐波那契数列（Fibonacci sequence），又称黄金分割数列，因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。它指的是这样一个数列：1、1、2、3、5、8、13、21、34、……这个数列从第3项开始，每一项都等于前两项之和。在数学上，斐波纳契数列被以递归的方法定义如下：

2 直接递归实现

使用公式f(n)=f(n-1)+f(n-2)，依次递归计算，递归结束条件是f(1)=1，f(2)=1。

核心代码如下：

这种方式可以以非常少的代码实现第N+1项的计算，但是与之相对的，这种算法的代价也非常高，计算机每次调用函数时，为了保证函数执行完毕，都必须将函数调用时的程序现场入栈保存，递归存在大量的自身调用，势必会产生非常庞大的函数现场栈来记录数据。

以求解f(10)作为例子来分析递归求解的过程。要求得f(10)，需要求得f(9)和f(8)。同样，要求得f(9)，要先求得f(8)和f(7)……用树形结构来表示这种依赖关系：

图1 递归求解的树形结构

不难发现在这棵树中有很多结点会重复的，而且重复的结点数会随着n的增大而急剧增加。