Python算法基础篇之斐波那契数列详解

写在前面

斐波那契数列这道题，说它是算法界的"Hello World"一点都不夸张。几乎每个学编程的人都写过，但能把这道题讲出花来的人不多。

我面试的时候被问过这道题不下五次，有的面试官让你写个递归就完事了，有的却追着问："还能优化吗？空间能不能到 O(1)？如果 n 是 10^18 怎么办？"一问一个准，没准备过的人当场就懵了。

这篇文章我会从最简单的递归开始，一路讲到矩阵快速幂，把斐波那契数列的五种解法全部过一遍。每种解法都配上代码、时间复杂度分析和适用场景。看完这篇，下次面试遇到这道题，你能从面试官手里反客为主。

一、斐波那契数列是什么？

先回顾一下定义：

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) (n >= 2)

数列的前几项是：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144…

这道题看起来简单，但它背后藏着很多有意思的东西。比如你可能不知道，斐波那契数列和黄金分割率有着千丝万缕的联系——当 n 越来越大时，F(n)/F(n-1) 会无限趋近于黄金分割率 φ ≈ 1.618。

而且斐波那契数在自然界中随处可见：百合花有 3 瓣花瓣，鸢尾有 3 瓣，雏菊有 34 瓣，向日葵的花盘有 55 个螺旋方向…这些数字都是斐波那契数。

好了，八卦到此为止，咱们进入正题。

二、解法一：递归（最直观，也最慢）

2.1 代码实现

def fib_recursive(n):
if n <= 1:
return n
return fib_recursive(n – 1) + fib_recursive(n – 2)

这段代码简洁优雅，几乎就是数学定义的直接翻译。但别被它的外表骗了——这代码慢得令人发指。

2.2 为什么慢？

我们以 fib(5) 为例，看看递归是怎么调用的：

fib(5)
├── fib(4)
│ ├── fib(3)
│ │ ├── fib(2)
│ │ │ ├── fib(1) → 1
│ │ │ └── fib(0) → 0
│ │ └── fib(1) → 1
│ └── fib(2)
│ ├── fib(1) → 1
│ └── fib(0) → 0
└── fib(3)
├── fib(2)
│ ├── fib(1) → 1
│ └── fib(0) → 0
└── fib(1) → 1

看到问题了吗？fib(3) 被算了 2 次，fib(2) 被算了 3 次！这些重复计算随着 n 的增大会呈指数级增长。

时间复杂度：O(2^n)
空间复杂度：O(n)（递归栈深度）

当 n = 30 时，递归调用次数已经超过 10 亿次。这代码在实际中根本没法用，但它作为教学例子非常经典——它完美展示了什么叫"重叠子问题"。

三、解法二：记忆化搜索（给递归加个缓存）

递归的问题在于重复计算。那如果我把算过的结果存起来，下次直接查表呢？

这就是记忆化搜索（Memoization）的核心思想。

3.1 代码实现

from functools import lru_cache

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

Python 的 functools.lru_cache 是个神器，它自动帮你做缓存。如果你不想用装饰器，也可以手动用字典实现：

def fib_memo_manual(n, memo=None):
if memo is None:
memo = {}
if n in memo:
return memo[n]
if n <= 1:
return n
memo[n] = fib_memo_manual(n – 1, memo) + fib_memo_manual(n – 2, memo)
return memo[n]

3.2 复杂度分析

加了缓存之后，每个 fib(n) 只会被计算一次。计算 fib(n) 需要知道 fib(n-1) 和 fib(n-2)，所以总共需要计算 n 个不同的值。

时间复杂度：O(n)
空间复杂度：O(n)（缓存字典 + 递归栈）

从 O(2^n) 到 O(n)，这提升不是一星半点。但记忆化搜索本质上还是递归，递归深度太大的时候（比如 n = 10000）会栈溢出。而且函数调用的开销也不小。

四、解法三：动态规划（自底向上填表）

既然递归是从上往下算（从 fib(n) 推到 fib(0)），那能不能反过来，从 fib(0) 开始往上推？

当然可以！这就是动态规划的自底向上思路。

4.1 代码实现

def fib_dp(n):
if n <= 1:
return n
dp = [0] * (n + 1)
dp[0] = 0
dp[1] = 1
for i in range(2, n + 1):
dp[i] = dp[i – 1] + dp[i – 2]
return dp[n]

4.2 复杂度分析

时间复杂度：O(n)
空间复杂度：O(n)（dp 数组）

和记忆化搜索相比，时间复杂度一样，但动态规划没有递归栈的开销，也不会出现栈溢出的问题。而且它更符合 DP 的"标准范式"——定义状态、找转移方程、填表、返回结果。

五、解法四：滚动变量（空间优化到 O(1)）

仔细观察动态规划的代码，你会发现一个规律：计算 dp[i] 的时候，只需要 dp[i-1] 和 dp[i-2] 两个值。更前面的值根本用不到。

那还存整个数组干嘛？用两个变量滚动更新就行了。

5.1 代码实现

def fib_optimized(n):
if n <= 1:
return n
prev2 = 0 # dp[i-2]
prev1 = 1 # dp[i-1]
for i in range(2, n + 1):
curr = prev1 + prev2 # dp[i] = dp[i-1] + dp[i-2]
prev2 = prev1 # 滚动：prev1 变成新的 prev2
prev1 = curr # curr 变成新的 prev1
return prev1

5.2 复杂度分析

时间复杂度：O(n)
空间复杂度：O(1)

这个版本是我面试时最推荐的写法。时间最优（O(n) 已经没法再低了，因为你至少要遍历一次），空间也最优（O(1)）。代码简洁，没有递归的坑，面试官看了也会点头。

六、解法五：矩阵快速幂（O(log n)，终极优化）

如果面试官继续追问：“n 很大怎么办？比如 n = 10^18？”

这时候 O(n) 的算法也不够用了。我们需要一个 O(log n) 的算法——矩阵快速幂。

6.1 数学原理

斐波那契数列可以用矩阵乘法表示：

[ F(n) ] [ 1 1 ] [ F(n-1) ]
[ F(n-1) ] = [ 1 0 ] × [ F(n-2) ]

设 M = [[1,1],[1,0]]，那么：

[ F(n) ] [ F(1) ] [ 1 ]
[ F(n-1) ] = M^(n-1) × [ F(0) ] = M^(n-1) × [ 0 ]

所以问题转化为：如何快速计算 M^(n-1)？

答案是快速幂。快速幂的核心思想是：

M^8 = M^4 × M^4
M^4 = M^2 × M^2
M^2 = M × M

只需要 log(n) 次矩阵乘法！

6.2 代码实现

def matrix_mult(A, B):
"""矩阵乘法"""
return [
[A[0][0]*B[0][0] + A[0][1]*B[1][0], A[0][0]*B[0][1] + A[0][1]*B[1][1]],
[A[1][0]*B[0][0] + A[1][1]*B[1][0], A[1][0]*B[0][1] + A[1][1]*B[1][1]]
]

def matrix_pow(M, n):
"""矩阵快速幂"""
if n == 1:
return M
if n % 2 == 0:
half = matrix_pow(M, n // 2)
return matrix_mult(half, half)
else:
return matrix_mult(M, matrix_pow(M, n – 1))

def fib_matrix(n):
if n <= 1:
return n
M = [[1, 1], [1, 0]]
result = matrix_pow(M, n – 1)
return result[0][0] # M^(n-1)[0][0] = F(n)

6.3 复杂度分析

时间复杂度：O(log n)
空间复杂度：O(log n)（递归栈，可以改迭代做到 O(1)）

这个算法在处理超大 n 时非常有用。比如 n = 10^18，O(n) 的算法要算一辈子，而矩阵快速幂只需要大约 60 次矩阵乘法。

七、五种解法综合对比

八、面试中的斐波那契数列

面试时这道题通常有几种问法，我按难度排个序：

Level 1：写出递归版本

这是送分题，但别写得太快。可以先写递归，然后主动说："但这个写法有重复计算的问题，我可以优化一下。"这样显得你有思考深度。

Level 2：优化到 O(n) 时间

写出滚动变量的版本。这是大多数面试官期望的答案。

Level 3：空间优化到 O(1)

滚动变量本身就是 O(1) 空间。如果面试官还问，说明他在考察你对空间复杂度的敏感度。

Level 4：n 很大怎么办？

这时候亮出矩阵快速幂。能讲到这一层，面试官基本会满意了。

Level 5：取模/大数问题

如果题目要求对 10^9+7 取模，注意矩阵乘法中的每个中间结果都要取模，防止溢出。

MOD = 10**9 + 7

def matrix_mult_mod(A, B):
return [
[(A[0][0]*B[0][0] + A[0][1]*B[1][0]) % MOD,
(A[0][0]*B[0][1] + A[0][1]*B[1][1]) % MOD],
[(A[1][0]*B[0][0] + A[1][1]*B[1][0]) % MOD,
(A[1][0]*B[0][1] + A[1][1]*B[1][1]) % MOD]
]

九、斐波那契数列的变种题目

掌握基础之后，可以挑战一些变种：

9.1 爬楼梯问题（LeetCode 70）

本质上就是斐波那契，dp[i] = dp[i-1] + dp[i-2]。

9.2 泰波那契数（LeetCode 1137）

T(n) = T(n-1) + T(n-2) + T(n-3)，用三个变量滚动即可。

9.3 第 N 个泰波那契数（LeetCode 1220）

更复杂的递推关系，但核心思想一样：找规律、定义状态、滚动优化。

9.4 斐波那契数列的第 n 项（剑指 Offer 10）

国内面试常考，和本文内容完全一致。

十、总结

斐波那契数列这道题看似简单，但深挖下去能引出很多算法思想：

• 递归：直观但低效，暴露重叠子问题
• 记忆化搜索：用空间换时间，缓存子问题结果
• 动态规划：自底向上填表，避免递归栈开销
• 空间优化：观察依赖关系，把 O(n) 空间压到 O(1)
• 矩阵快速幂：数学变形，把 O(n) 时间压到 O(log n)

这些思想不仅适用于斐波那契，也是解决其他 DP 问题的通用套路。

最后再强调一下面试策略：

这样一套组合拳打下来，面试官想不给你过都难。

如果这篇文章对你有帮助，欢迎点赞收藏！有任何问题可以在评论区留言，我会尽量回复。后续会持续更新算法面试相关的干货内容，欢迎关注！