异常教程

Python 打印斐波那契数列（长文讲解）

更新时间:

💡一则或许对你有用的小广告

欢迎加入小哈的星球 ，你将获得：专属的项目实战 / 1v1 提问 / Java 学习路线 / 学习打卡 / 每月赠书 / 社群讨论

截止目前， 星球 内专栏累计输出 90w+ 字，讲解图 3441+ 张，还在持续爆肝中.. 后续还会上新更多项目，目标是将 Java 领域典型的项目都整一波，如秒杀系统, 在线商城, IM 即时通讯，权限管理，Spring Cloud Alibaba 微服务等等，已有 3100+ 小伙伴加入学习 ，欢迎点击围观

前言

斐波那契数列是编程领域最经典的数列之一，其递推关系简洁却蕴含丰富的数学规律。对于编程初学者而言，它是一个绝佳的练习项目，既能巩固循环和递归的基础知识，又能理解算法效率的差异。而对于中级开发者，通过优化斐波那契数列的生成方式，可以深入学习动态规划、生成器以及装饰器等进阶概念。本文将以 Python 打印斐波那契数列为核心，通过循序渐进的方式，从基础实现到优化技巧，帮助读者全面掌握这一主题。

什么是斐波那契数列？

斐波那契数列（Fibonacci Sequence）是由意大利数学家列昂纳多·斐波那契在1202年提出的，其定义如下：

  • 前两项为 F(0) = 0 和 F(1) = 1
  • 后续项满足递推公式：F(n) = F(n-1) + F(n-2)

例如，前10项为：
0, 1, 1, 2, 3, 5, 8, 13, 21, 34

这个数列在自然界（如向日葵种子排列）、金融模型等领域都有广泛应用。接下来，我们将通过 Python 代码实现这一数列的打印。

方法一：循环（迭代法）

原理与步骤

循环是最直观的实现方式，适合编程初学者理解。其核心思想是：

  1. 从已知的前两项开始
  2. 通过循环逐项计算后续数值
  3. 将结果存储在列表中，最终打印输出

示例代码

def print_fibonacci(n):
    if n <= 0:
        print("请输入大于0的整数")
        return
    
    fib_sequence = [0, 1]  # 初始化前两项
    
    # 循环从第三项开始计算
    for i in range(2, n):
        next_num = fib_sequence[i-1] + fib_sequence[i-2]
        fib_sequence.append(next_num)
    
    print(f"前{n}项斐波那契数列为：{fib_sequence[:n]}")

print_fibonacci(10)

代码解析

  • 参数验证：首先检查输入是否合法（n > 0）。
  • 初始化列表：fib_sequence 存储数列，初始值为 [0, 1]。
  • 循环计算：从索引 2 开始，每一项等于前两项之和。
  • 输出结果：通过 [:n] 确保输出项数与输入参数一致。

优点：时间复杂度为 O(n)，效率高且内存占用可控。

方法二：递归法

原理与步骤

递归是另一种实现斐波那契数列的方法，其核心思想是：

  • 数学定义直接映射：F(n) = F(n-1) + F(n-2)
  • 终止条件：当 n=0 或 n=1 时直接返回结果

示例代码

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

for i in range(10):
    print(f"F({i}) = {fibonacci_recursive(i)}")

代码解析

  • 递归函数：直接通过函数调用自身实现递推。
  • 终止条件：确保递归在 n=0 或 n=1 时停止。

缺点：时间复杂度为 O(2ⁿ)，当 n 较大时（如 n=40），计算会非常缓慢。这是因为递归会重复计算大量子问题，例如 F(40) 需要计算 F(39) 和 F(38)，而 F(39) 又需要重新计算 F(38) 和 F(37)，导致效率极低。

形象比喻：递归的低效就像俄罗斯套娃，每个大套娃需要拆开所有小套娃才能看到最小的那个，而循环则是直接一层层打开，效率更高。

方法三：递归 + 缓存优化

原理与步骤

为解决递归的低效问题，可以通过缓存（记忆化）存储已计算的结果。Python 的 lru_cache 装饰器可以轻松实现这一优化：

示例代码

from functools import lru_cache

@lru_cache(maxsize=None)  # 启用缓存
def fibonacci_memoized(n):
    if n == 0:
        return 0
    elif n == 1:
        return 1
    else:
        return fibonacci_memoized(n-1) + fibonacci_memoized(n-2)

for i in range(40):
    print(f"F({i}) = {fibonacci_memoized(i)}")

代码解析

  • 装饰器 lru_cache：自动缓存函数的返回值，避免重复计算。
  • 时间复杂度：优化后变为 O(n)，与循环法效率相当。

适用场景：当需要多次调用斐波那契函数时（例如在算法题中），缓存能显著提升性能。

方法四：生成器模式

原理与步骤

生成器（Generator）是一种惰性求值的迭代工具，适合处理大数据量或无限序列。斐波那契数列的生成器实现如下：

示例代码

def fibonacci_generator():
    a, b = 0, 1
    while True:
        yield a
        a, b = b, a + b

fib = fibonacci_generator()
for _ in range(10):
    print(next(fib))

代码解析

  • 生成器函数：通过 yield 关键字返回值，但不会立即终止函数。
  • 惰性求值：每次调用 next() 才计算下一个值，节省内存。

优势：适用于生成无限序列（如数列的前1000项），无需预先存储所有数值。

方法五：动态规划

原理与步骤

动态规划（Dynamic Programming）通过自底向上的方式，将子问题的解存储在数组中，避免重复计算。

示例代码

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

print(fibonacci_dp(10))

代码解析

  • 预分配数组：通过 fib = [0] * (n+1) 初始化空间。
  • 逐步填充：从 i=2 开始，逐项计算并存储结果。

时间复杂度：O(n)，与循环法类似，但空间复杂度更高（需存储所有中间结果）。

方法对比与选择指南

方法实现方式时间复杂度空间复杂度适用场景
循环迭代法迭代循环O(n)O(n)大部分场景，推荐使用
递归法递归调用O(2ⁿ)O(n)小规模数据或教学演示
递归 + 缓存递归 + 装饰器O(n)O(n)需要多次调用斐波那契函数时
生成器生成器函数O(n)O(1)处理无限序列或大数据量
动态规划数组存储中间结果O(n)O(n)需要完整序列且空间允许时

进阶优化：数学公式法

斐波那契数列的通项公式可通过黄金分割率推导：
$$
F(n) = \frac{\phi^n - (1-\phi)^n}{\sqrt{5}}
$$
其中，$\phi = \frac{1+\sqrt{5}}{2} \approx 1.618$（黄金比例）。

示例代码

import math

def fibonacci_formula(n):
    phi = (1 + math.sqrt(5)) / 2
    return round( (phi**n - (1-phi)**n) / math.sqrt(5) )

for i in range(10):
    print(f"F({i}) = {fibonacci_formula(i)}")

代码解析

  • 数学公式：直接计算第 n 项的值，无需循环或递归。
  • 四舍五入：由于浮点数精度限制，需通过 round() 处理。

适用性：仅对单个项的快速计算有效，不适合生成完整序列。

常见问题与解决方案

1. 递归导致栈溢出

当 n 较大时（如 n=1000），递归会因栈深度过大而报错：

RecursionError: maximum recursion depth exceeded

解决方案：改用循环法或生成器，或通过 sys.setrecursionlimit() 增加递归深度（不推荐）。

2. 大数溢出问题

斐波那契数列增长极快，当 n 超过 1000 时，数值会超出 Python 的整数范围。
解决方案：Python 的 int 类型支持大整数运算，无需额外处理。

3. 性能对比

方法计算 F(40) 的时间（秒）
循环迭代法<0.001
递归法>1000
递归 + 缓存<0.001
动态规划<0.001

结论

通过本文的讲解，我们掌握了 Python 打印斐波那契数列 的多种实现方法，包括循环、递归、生成器、动态规划和数学公式等。针对不同场景选择合适的方法至关重要：

  • 基础场景：推荐使用循环或生成器，代码简洁且效率高。
  • 算法优化：通过缓存或动态规划解决递归的低效问题。
  • 数学挑战：利用通项公式实现单次快速计算。

希望本文能帮助读者不仅掌握斐波那契数列的实现，更能理解不同算法设计的思想与权衡。在后续的学习中，可以尝试将这些方法应用到其他递推问题（如阶乘、汉诺塔等），进一步巩固编程与算法基础。

最新发布

查看更多文章