Python 实现斐波那契数列

斐波那契数列简介

斐波那契数列（Fibonacci sequence）是一个经典的数学序列，其定义如下：

• 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...

Python 实现方法

1. 递归实现

示例代码 - shift

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

特点：

• 代码简洁直观
• 时间复杂度为 O(2^n)，效率较低
• 适合理解递归概念但不适合大规模计算

2. 迭代实现

示例代码 - shift

def fibonacci_iterative(n):
    a, b = 0, 1
    for _ in range(n):
        a, b = b, a + b
    return a

特点：

• 时间复杂度为 O(n)
• 空间复杂度为 O(1)
• 适合实际应用场景

3. 动态规划实现

示例代码 - shift

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

特点：

• 时间复杂度 O(n)
• 空间复杂度 O(n)
• 可扩展性强，适合更复杂的动态规划问题

性能比较

当 n=35 时：

• 递归方法：约 900 万次函数调用，耗时明显
• 迭代方法：35 次循环，几乎瞬间完成

实际应用场景

1. 金融分析：黄金分割比计算
2. 算法设计：动态规划问题
3. 计算机图形学：自然生长模式模拟
4. 音乐创作：音符排列组合

优化建议

对于需要多次调用的情况，可以考虑：

• 使用缓存装饰器（Python 的 @lru_cache）
• 预计算并存储结果
• 使用矩阵快速幂算法（时间复杂度 O(log n)）

示例代码 - shift

from functools import lru_cache

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