第 27 课 · 阶段四 · 函数与模块

递归函数

函数自己调用自己就是递归。这一课理解递归的两大要素，用阶乘、斐波那契吃透它，并学会避免栈溢出。

第 27 课阶段四 · 函数与模块难度：进阶建议时长：30 分钟关键词：递归 · 基线条件 · 阶乘 · 斐波那契

🎯 学完本课你将掌握

理解递归的原理与两个要素
写出阶乘与斐波那契的递归实现
识别递归深度限制并避免栈溢出

一、什么是递归

递归 = 函数调用自己。它像俄罗斯套娃：解决大问题前先解决缩小版的小问题，直到小到可以直接给出答案。

二、递归两大要素

基线条件（出口）：最简情况直接返回，不再递归。
递归条件：把问题缩小一步，然后调用自己。

三、经典案例：阶乘

n! = n × (n-1) × ... × 1，且 0! = 1。递归思路：n! = n × (n-1)!。

阶乘.py

1def fact(n):
2    if n <= 1:          # 基线条件
3        return 1
4    return n * fact(n - 1)   # 递归条件
5
6print(fact(5))   # 120
7print(fact(0))   # 1

四、执行过程拆解

fact(5) = 5 × fact(4) = 5 × 4 × fact(3) = ... = 5 × 4 × 3 × 2 × 1 = 120。每次调用都把问题缩小，直到触底再一路乘回来。

五、经典案例：斐波那契

斐波那契.py

1def fib(n):
2    if n <= 1:           # F(0)=0, F(1)=1
3        return n
4    return fib(n - 1) + fib(n - 2)
5
6for i in range(8):
7    print(fib(i), end=" ")
8# 0 1 1 2 3 5 8 13

⚠️ 注意

朴素斐波那契递归有大量重复计算（fib(40) 会非常慢）。性能敏感时改用循环或加缓存（functools.lru_cache）。

六、递归 vs 循环

对比	递归	循环
写法	简洁、接近数学定义	显式、易理解
性能	有函数调用开销	通常更快
风险	可能栈溢出	无此风险
适用	树、分治、搜索等	线性重复

七、避免栈溢出

递归深度.py

1import sys
2print(sys.getrecursionlimit())   # 默认约1000
3
4def count(n):
5    if n == 0:
6        return
7    count(n - 1)
8# count(100000)   # 会 RecursionError，别运行！

八、常见错误与解决

常见错误与解决

错误现象	原因 / 解决方法
`RecursionError: maximum recursion depth exceeded`	没有基线条件或基线没触发，导致无限递归；检查出口。
`返回值全错`	递归公式写错，先用小数字手推验证 base 与递推式。
`性能极差`	重复计算太多，改用循环或记忆化缓存。

✍️ 小练习

用递归求 1+2+...+100；再用递归反转一个字符串（提示：s[0] 与 s[1:] 的关系）。

📌 本节小结

递归两大要素：基线条件 + 缩小问题；阶乘、斐波那契是必会案例；注意递归深度与性能。能用递归优雅解决的往往是“树形/分治”问题。