1 定义
斐波那契数列（Fibonacci sequence），又称黄金分割数列、因数学家列昂纳多·斐波那契（Leonardoda Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”，指的是这样一个数列：1、1、2、3、5、8、13、21、34、……
规律是：这个数列从第3项开始，每一项都等于前两项之和。
2 代码
递推法
滚动变量，产生数据量少。
def fib(n):a, b = 1, 1for i in range(n-1):a, b = b, a+breturn a |
|---|
递归法
编写代码量少，但随数据增大，产生大量数据，效率会非常低。
def fib(n):return n <= 2 and 1 or fib(n-1)+fib(n-2) |
|---|
矩阵法
根据数列从第3项开始，每一项都等于前两项之和这一规律列式：
import numpydef fib(n):return (numpy.matrix([[1, 1], [1, 0]]) ** (n - 1) * numpy.matrix([[1], [0]]))[0, 0] |
|---|
3 总结
上面三种方法在数据小的情况下效率差不多，前两种方法更容易思考，编写的代码量少且结构简单，特别是递归法。但随着数据的增大，递归产生大量数据，效率会非常低，递推法中变量是滚动的，不会产生太大数据。而矩阵法快速相乘的效率会比其他两种方法更好。
