斐波那契数列的4种Python实现——从递归到矩阵，面试必备基础算法

（改编自 鲁迅《孔乙己》）

孔乙己自己知道不能和他们谈天，便只好向 Intern 说话。有一回对我说道，“你写过代码么？”我略略点一点头。他说，“写过代码，……我便考你一考。斐波那契数列的输出，怎样实现？”我想，讨饭一样的人，也配考我么？便回过脸去，不再理会。孔乙己等了许久，很恳切的说道，“不能写罢？……我教给你，记着！这些代码应该记着。将来做 Leader 的时候，开发项目要用。”我暗想我和 Leader 的等级还很远呢，而且我们 Leader 也从不在项目里写斐波那契；又好笑，又不耐烦，懒懒的答他道，“谁要你教，不是递归么？”孔乙己显出极高兴的样子，将两个指头的长指甲敲着键盘，点头说，“对呀对呀！……斐波那契有四样写法，你知道么？”我愈不耐烦了，努着嘴走远。孔乙己刚在命令行打开 Vim，想在里面写代码，见我毫不热心，便又叹一口气，显出极惋惜的样子。

“算法题”是很多程序员面试时绕不开的一关，今天我们就来看看，如何用 Python 输出斐波那契数列。

什么是斐波那契数列？

斐波那契（Fibonacci）数列，又称黄金分割数列，因数学家列昂纳多·斐波那契（Leonardo Fibonacci）以兔子繁殖为例子而引入，故又称为“兔子数列”。它指的是这样一个数列：

1、1、2、3、5、8、13、21、34……

在数学上，斐波那契数列通常用递推方式定义：

• F(1) = 1
• F(2) = 1
• F(n) = F(n - 1) + F(n - 2) （n ≥ 3，n ∈ N*）

简单来讲就是：数列中某一项的值，都等于前两项之和。

在现代物理、准晶体结构、化学等领域，斐波纳契数列都有直接的应用。为此，美国数学会从 1963 年起出版了以《斐波纳契数列季刊》为名的一份数学杂志，专门刊载这方面的研究成果。（摘自百度百科）

我也曾经把手写斐波那契作为面试题之一。用代码实现它的方法有很多，下面来讲几个常见的实现。

1. 递归

在很多编程教程中提到斐波那契数列，通常都是用它来讲解递归函数。当一个问题可以不断拆分为规模更小的同类问题时，就可以考虑使用递归。

def fib_1(n):
    if n <= 1:
        return 1
    return fib_1(n-1) + fib_1(n-2)

for i in range(20):
    print(fib_1(i), end=' ')

不过，这种写法在 n > 30 后就会出现肉眼可见的卡顿，甚至内存溢出而报错——这是因为过程中存在大量的重复计算。为了解决这个问题，我们可以利用 Python 内置的缓存装饰器。

from functools import lru_cache

@lru_cache(maxsize=None)
def fib_1(n):
    if n <= 1:
        return 1
    return fib_1(n-1) + fib_1(n-2)

for i in range(20):
    print(fib_1(i), end=' ')

2. 循环

斐波那契并不一定非要依赖递归来实现。很多递归逻辑，其实都可以改写成循环的方式。这也能帮助我们更直接地理解“每一项等于前两项之和”这个核心递推关系。

def fib_2(n):
    a, b = 0, 1
    for i in range(n):
        print(b, end=' ')
        a, b = b, a + b

fib_2(20)

3. 生成器

生成器的实现思路本质上与循环类似，只是运用了 yield 关键字，让函数变成迭代器，在需要时才生成数值，非常适合按需计算的场景。

def fib_3(n):
    a, b = 0, 1
    while n > 0:
        yield b
        a, b = b, a + b
        n -= 1

for i in fib_3(20):
    print(i, end=' ')

4. 矩阵相乘

除了常规的算法思维，斐波那契数列还有一些更“数学化”的实现方式。例如，利用二阶矩阵的相乘来推导：

借助 Python 的 NumPy 库就能简洁地表达这种矩阵幂计算：

import numpy as np

def fib_4(n):
    base = np.array([[1, 1], [1, 0]], dtype='int64')
    for i in range(n):
        res = np.linalg.matrix_power(base, i) @ np.array([[1], [0]])
        print(int(res[0][0]), end=' ')

fib_4(20)

上述 4 种方法的输出结果都是：

1 1 2 3 5 8 13 21 34 55 89 144 233 377 610 987 1597 2584 4181 6765

斐波那契数列的实现方法远不止这 4 种。如果你有其他的实现，欢迎在留言中补充。