在 Python 中实现斐波那契数列（Fibonacci sequence）是一个非常经典的问题，下面我将为你展示几种不同的实现方法，从最简单直观到最高效,并解释它们的优缺点。
（图片来源网络，侵删）
什么是斐波那契数列？
斐波那契数列是一个整数序列，通常以 0 和 1 开始，之后的每一项都是前两项之和,数学上定义为：
- F(0) = 0
- F(1) = 1
- F(n) = F(n-1) + F(n-2) (当 n > 1 时)
这个数列的前几项是：0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ...
递归实现
这是最符合数学定义、最直观的方法,函数直接调用自身来计算前一项和前前一项。
代码实现
def fibonacci_recursive(n):
"""
使用递归方法计算斐波那契数列的第 n 项。
注意：这种方法效率极低，仅用于理解概念。
"""
# 基本情况：处理数列的开头两项
if n <= 1:
return n
# 递归步骤：调用函数自身
else:
return fibonacci_recursive(n - 1) + fibonacci_recursive(n - 2)
# --- 使用示例 ---
# 计算第 10 项
n = 10
result = fibonacci_recursive(n)
print(f"使用递归计算第 {n} 项斐波那契数是: {result}") # 输出: 55
# 计算第 15 项
n = 15
result = fibonacci_recursive(n)
print(f"使用递归计算第 {n} 项斐波那契数是: {result}") # 输出: 610
优点
- 代码简洁：非常直观地反映了斐波那契的数学定义。
- 易于理解：对于初学者来说,是理解递归思想的好例子。
缺点
- 效率极低：存在大量的重复计算，计算
fib(5)时，fib(3)会被计算两次，fib(2)会被计算三次，当n变大时,计算时间会呈指数级增长。 - 栈溢出风险：Python 有递归深度限制（默认约 1000），当
n过大时，会导致RecursionError。
迭代实现（推荐）
这是最常用且最高效的方法之一，它使用循环，从数列的开头开始，逐步计算出每一项,直到目标项。
代码实现
def fibonacci_iterative(n):
"""
使用迭代（循环）方法计算斐波那契数列的第 n 项。
这是最高效和最常用的方法之一。
"""
# 处理基本情况
if n <= 1:
return n
# 初始化前两项
a, b = 0, 1
# 循环 n-1 次，因为已经知道了第 0 和第 1 项
# 循环结束后，b 的值就是第 n 项
for _ in range(n - 1):
# a, b = b, a + b 是一个简洁的 Python 写法
# 它等同于：
# next_value = a + b
# a = b
# b = next_value
a, b = b, a + b
return b
# --- 使用示例 ---
# 计算第 10 项
n = 10
result = fibonacci_iterative(n)
print(f"使用迭代计算第 {n} 项斐波那契数是: {result}") # 输出: 55
# 计算第 100 项
n = 100
result = fibonacci_iterative(n)
print(f"使用迭代计算第 {n} 项斐波那契数是: {result}") # 输出: 354224848179261915075
优点
- 效率极高：时间复杂度为 O(n)，只需要一次循环,没有重复计算。
- 不会栈溢出：不依赖递归，可以计算非常大的
n值（仅受限于整数的大小和内存）。 - 内存占用少：只使用了固定的几个变量来存储中间结果。
缺点
- 相比递归，代码逻辑稍微不那么“数学化”,但依然非常清晰。
记忆化递归
这是一种优化递归的方法，它使用一个“缓存”（比如字典）来存储已经计算过的结果,避免重复计算。
代码实现
# 使用字典作为缓存
memo = {0: 0, 1: 1}
def fibonacci_memoization(n):
"""
使用记忆化递归方法计算斐波那契数列的第 n 项。
它结合了递归的简洁性和迭代的效率。
"""
# 如果结果不在缓存中，则进行计算
if n not in memo:
# 递归调用，并将结果存入缓存
memo[n] = fibonacci_memoization(n - 1) + fibonacci_memoization(n - 2)
# 从缓存中返回结果
return memo[n]
# --- 使用示例 ---
# 清空缓存，以防多次调用时数据混乱
memo.clear()
memo = {0: 0, 1: 1}
n = 50
result = fibonacci_memoization(n)
print(f"使用记忆化递归计算第 {n} 项斐波那契数是: {result}") # 输出: 12586269025
优点
- 效率高：时间复杂度降为 O(n),因为每个斐波那契数只被计算一次。
- 代码简洁：保留了递归的清晰结构。
缺点
- 需要额外内存：需要一个缓存来存储计算结果，空间复杂度为 O(n)。
- 对于非常大的
n，递归深度限制问题依然存在（但比普通递归好得多）。
使用生成器
如果你需要生成斐波那契数列中的所有数字，而不仅仅是第 n 项，使用生成器是最佳选择，它可以在不一次性占用大量内存的情况下,逐个产生数列中的数字。
代码实现
def fibonacci_generator():
"""
一个斐波那契数列的生成器函数。
可以逐个产生数列中的数字。
"""
a, b = 0, 1
while True:
yield a # 产生当前值
a, b = b, a + b # 准备下一个值
# --- 使用示例 ---
# 创建一个生成器对象
fib_gen = fibonacci_generator()
# 打印前 10 个斐波那契数
print("斐波那契数列的前 10 项是:")
for i in range(10):
print(next(fib_gen))
# 输出:
# 0
# 1
# 1
# 2
# 3
# 5
# 8
# 13
# 21
# 34
# 获取第 100 项（通过循环99次）
for i in range(99):
next(fib_gen)
print("\n使用生成器获取的第 100 项是:", next(fib_gen)) # 输出: 354224848179261915075
优点
- 内存效率极高：任何时候内存中只存在数列中的两个数字,非常适合处理无限序列或非常大的序列。
- 代码优雅：是处理序列化数据的 Pythonic 方式。
缺点
- 如果你的目标只是计算第
n项，它需要循环n次,比直接迭代计算稍微多了一层抽象。
总结与如何选择
| 方法 | 时间复杂度 | 空间复杂度 | 优点 | 缺点 | 适用场景 |
|---|---|---|---|---|---|
| 递归 | O(2^n) | O(n) | 代码直观，易于理解 | 效率极低，易栈溢出 | 学习递归概念，不用于生产环境 |
| 迭代 | O(n) | O(1) | 效率最高，内存占用少 | 逻辑比递归稍复杂 | 强烈推荐，计算第 n 项的首选方法。 |
| 记忆化递归 | O(n) | O(n) | 代码简洁，效率高 | 需要额外内存，仍有递归深度限制 | 当你喜欢递归风格且需要优化时。 |
| 生成器 | O(n) (获取第n项) | O(1) | 内存效率极高，优雅 | 获取特定项不如迭代直接 | 需要逐个处理数列中的所有数字时。 |
给你的建议：
- 如果你是初学者：先理解递归方法,因为它最直观。
- 在实际项目中：请使用迭代 (
fibonacci_iterative) 方法,因为它在性能和内存上都是最优的。 - 如果你需要处理一个很长的序列：使用生成器 (
fibonacci_generator) 方法。
