虽然 Fabonacci 不是 LeetCode 中的题，但是也是一道比较经典的题目，好久不看就会忘掉，今天总结一下四种实现 Fibonacci 数列的方法，编程语言为 Python。
Fabonacci 公式
$$f(n) = \begin{cases}0,& n = 0; \\ 1,& n = 1; \\ f(n-1) + f(n-2),&n>1.\end{cases}$$
第一种：递归
递归思想最大的优点就是逻辑简单清晰，但是它在 python 中也会引起 递归深度 问题，毕竟递归深度越深对系统资源的占用也越大，很容易导致栈溢出。python 的默认最大递归深度为 1000，修改的方法如下：
import sys
sys.setrecursionlimit(1000000)所以即使递归思想很重要，也不太提倡使用。
下面为递归解法：
def fibonacci_tool(n):
#1. 设定递归基线条件
if n <= 0:
return 0
elif n == 1:
return 1
#2. 设定递归条件
else:
return fibonacci_tool(n - 1) + fibonacci_tool(n - 2)
def fibonacci(n):
for i in range(1,n+1):
print(fibonacci_tool(i))但是有一个问题我们很容易发现，那就是在计算 $f(n) = f(n-1) + f(n-2)$ 的时候，为了计算得到 $f(n)$ 我们每次都要计算之前的所有值，这样造成了极大的资源浪费，最好的解决办法就是循环。
第二种：循环
def fibonacci_(n):
a = 0
b = 1
i = 0
while i < n:
print(a)
a,b = b,a+b
i += 1循环对于 fibonacci 而言是一种相对简单的解法，不会出现递归带来的大量资源浪费现象。
第三种：迭代
在使用 递归 方法时由于会出现大量的重复计算(如下图所示)，这样的重复计算随着 n 的逐渐增大而急剧增加，造成大量的资源浪费。
f(10)
/ \
f(9) f(8)
/ \ / \
f(8) f(7) f(7) f(6)
/ \ / \
f(7) f(6) f(6) f(5)但是迭代的思想就是不断地用变量的旧值递推新值的过程。迭代法相对于递归效率要高，因为节省了重复计算。
代码如下：
def fibonacci(n):
list_fibo = [0,1]
for i in range(n - 2):
list_fibo.append(list_fibo[-2] + list_fibo[-1])
return list_fibo第四种：矩阵
还有一种方法就是将计算公式转到矩阵运算上来，在 python 中可以利用 numpy 加速矩阵运算，具体的实现方式有点类似求多项式的通项公式，详细如下：
首先：$f(0) = 0;f(1) = 1$；我们将相邻的两项转换成 2x1 的矩阵:
$\begin{bmatrix}f_{n}\\f_{n-1}\end{bmatrix}$ = $\begin{bmatrix}f_{n-1} + f_{n-2}\\f_{n-1}\end{bmatrix}$ = $\begin{bmatrix}1\times f_{n-1} + 1 \times f_{n-2}\\1 \times f_{n-1} + 0 \times f_{n-2}\end{bmatrix}$ = $\begin{bmatrix}1&1\\1&0\end{bmatrix}$ $\times$ $\begin{bmatrix}f_{n-1}\\f_{n-2}\end{bmatrix}$ = $\begin{bmatrix}1&1\\1&0\end{bmatrix}^{n-1} \times \begin{bmatrix}f_{1}\\f_{0}\end{bmatrix}$
= $\begin{bmatrix}1&1\\1&0\end{bmatrix}^{n-1} \times \begin{bmatrix}1\\0\end{bmatrix}$
求F(n)等于求二阶矩阵的n - 1次方，结果取矩阵第一行第一列的元素。
代码如下：
import numpy as np
def fibonacci(n):
Matrix = np.matrix("1 1;1 0")
results = []
for i in range(0,n):
results.append(np.array(pow(Matrix,i))[0][0])
return results