斐波那契数列通项公式（Fibonacci sequence）又稱黄金分割数列，这个数列最早是由印度数学家提出来的不过更多的人学习到这个数列是因为意大利数学家列昂纳多·斐波那契（Leonardoda Fibonacci）和怹的《Liber Abaci》一书。在这本书中列昂纳多·斐波那契以兔子繁殖为例子引出了这个序列，因此这个序列又称为“兔子数列”。
在数学上，斐波纳契数列以如下被以递归的方法定义：

Fibonacci 数列除了递归形式之外当然还可以写出通项公式。下面就来算算 F(n)

是典型的线性差分方程，可以用经典的待定系数法来解当然也可以用

变换解。考虑到不是每个人都学过

变换这里就给个最基本的待定系数法。假設

是两个待定系数那么有：

这是一个简单的二元一次方程，计算后可以得到：

有些没有学过差分方程理论的同学可能会问为什么假设 F(n)=C×Wn简单的说，这是猜的当然也不是无缘无故的猜测。我们知道

我们再构造两个辅助的差分方程：

斐波纳契数列的定义是递归形式的自然，用递归函数最容易实现

这个代码虽然简单，但是计算复杂度却太高当 n 稍微大一点时，计算时间就会非常长

我们用 B(n) 表示 F(n) Φ多少次调用自己。那么就有递归表达式：

那么这个 B(n) 具体是多少呢 显而易见，当 n≥2

如果将递归算法改为递推时间复杂度会降低很多。

這个程序很简答for 循环中计算了n?2 次， 所以时间复杂度为 O(n)

那么原来的递归算法就没有改进的余地了吗？递归算法之所以算的慢是因为計算F(n) 时，对于小于 n 的数 m重复计算了很多次F(m)。下面这幅图给出了计算 F(6) 时的递归调用关系

都重复计算了好几遍。其实只要将计算过的F(m) 保存下来，下次用时直接读取就好了这样就省去了反复计算 F(m) 的问题。下面是改进后的代码时间复杂度降低为 O(n)：

这个代码还用到了 static 型局部數据变量的一个特性：没有指定值的元素自动初始化为 0。如果没有这个特性我们的程序中就要写上 255 个 0 了。

除了上面给出的两种 O(n) 算法之外还有没有更快的计算 F(n) 的方法呢？ 答案是肯定的
我们将递推表达式变变型就能得到：

因此，计算 F(n) 就变成了计算一个矩阵的 n?1 次方的问题叻而这个问题是有快速算法的。
所以只要计算出了 Mn/2 了之后再自乘一下就行了
所以只要计算出了 M(n?1)/2 了之后自乘一下在加一下自己就可以叻。

也就是说当 n=2m 时只需要进行 m 次乘法计算就可以了。当 n<2m 时最多也就是进行 m 次乘法计算 和 次加法计算。所以算法复杂度是 较大时log(n)?n，所以当 n 较大时这样计算会快的多这里就不写出这种算法的具体实现了，感兴趣的同学可以自己写写

这里还有一个问题一直没有解决，僦是我们的程序可以正确计算到 n 为多少 我们知道一个 m 位的无符号整数可以表示的最大的整数是 2m?1。当 F(n)>2m?1 自然计算结果就是错误的了 估計这个最大的 n 还要用到我们上面给出的通项公式的近似结果：

所以 32 位无符号整数最大可以表示到 F(47)，64 位无符号整数最大可以表示到