Python 进阶 - 第十六节

📋 本节要点

知识点	说明
递归函数	函数内部调用自身
递归三要素	终止条件、规模缩小、调用自身
调用栈	递归的压栈和出栈过程
递归深度	默认约1000层限制
递归 vs 迭代	各自适用场景

1. 什么是递归？

递归就是函数内部调用自身。核心思想：把大问题拆成相似的子问题，直到问题简单到可以直接解决。

递归三要素：
① 终止条件（base case）：问题最简形式，直接返回结果
② 规模缩小：每次调用都向终止条件靠近
③ 调用自身：用同样的方法解决子问题

def func(n):
    if 终止条件:        # ① 递归出口
        return 结果
    return func(更小的n)  # ②③ 缩小规模并调用自身

2. 经典案例：阶乘

n! = n × (n-1) × (n-2) × ... × 1，例如 5! = 5×4×3×2×1 = 120

def factorial(n):
    if n == 1:        # 终止条件
        return 1
    return n * factorial(n - 1)  # 缩小规模并调用自身

print(factorial(5))  # 120
print(factorial(3))  # 6

调用过程：

factorial(5) → 5 * factorial(4) → 5 * 4 * factorial(3) → ... → 5×4×3×2×1 = 120

3. 经典案例：斐波那契数列

数列：1, 1, 2, 3, 5, 8, 13... 每一项等于前两项之和。

def fibonacci(n):
    if n <= 1:          # 终止条件
        return n
    return fibonacci(n-1) + fibonacci(n-2)

for i in range(1, 8):
    print(f"F({i}) = {fibonacci(i)}")

运行结果： F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(6)=8, F(7)=13

4. 递归的调用栈

递归的"先递后归"过程：

def countdown(n):
    if n == 0:
        print("Go!")
        return
    print(n, end=" ")
    countdown(n - 1)
    print(f"[返回{n}]", end=" ")

countdown(3)  # 输出：3 2 1 Go! [返回1] [返回2] [返回3]

调用栈变化：每次调用压入栈帧 → 到达终止条件 → 逐层弹出返回。递归深度过大时会触发 RecursionError: maximum recursion depth exceeded。

5. 递归 vs 迭代

对比	递归	迭代
代码	简洁，逻辑清晰	较复杂
性能	较低（函数调用开销）	较高
内存	占用多（调用栈）	占用少
适合场景	树形遍历、分治问题	简单循环计算

经验原则：能用迭代优先用迭代；递归适合问题本身具有递归结构（如文件目录遍历、树形数据）。

下一节预告：匿名函数与偏函数

Python进阶4-递归函数