第 18 章 套娃大法:递归
📖 本章目标:理解递归思想,掌握递归三要素,会写阶乘、斐波那契和递归求和。
学完本章,你会进入一个新境界——让函数自己调用自己。
递归是编程里最优雅、也最容易把人绕晕的一招。它像俄罗斯套娃:打开一层,里面还是同样的娃娃。掌握了它,你会多一种看待问题的"分身视角"。
【开场小剧场】俄罗斯套娃
学生: 皮皮,你说函数能调用另一个函数,那……函数能调用自己吗?
皮皮: 能,而且这叫递归,是编程里最优雅也最容易绕晕的招式。你玩过俄罗斯套娃吗?打开最大的娃娃,里面是个小一号的娃娃,再打开,又小一号……直到最小的那个。
学生: 递归就是套娃?
皮皮: 对。递归的精髓就是:把一个大问题,拆成"一个小问题 + 一个更小的同款问题"。 直到小到不用再拆为止。
学生: 那最小的娃娃不就"卡住"了?
皮皮: (竖起一根手指)这就是关键!最小的那个娃娃就是出口——不用再拆了,直接回答。没有出口的套娃,你拆到天荒地老也停不下来。
18.1 递归:函数调用自己
最简单的递归长这样:
def countdown(n):
print(n)
countdown(n - 1) # 自己调用自己!
但是——这个函数会无限调用下去,直到报错(后面会讲)。递归必须有一个"出口"。
先看一个会正常结束的:数到 1 就停:
def countdown(n):
if n <= 0: # ① 出口:什么时候不再递归
return
print(n) # ② 干当前这件事
countdown(n - 1) # ③ 处理更小一号的问题
countdown(3)
运行结果:
3
2
1
逐行拆解:
- if n <= 0: return:出口。当 n 小到 0 时,不再递归,直接结束;
- print(n):先做"当前这一层"的活;
- countdown(n - 1):派一个"分身"去处理小一号的问题(处理 n-1);
- 于是 countdown(3) 先打印 3,再让分身去处理 countdown(2)……
它是怎么"往回跑"的?
countdown(3):
打印 3 → 调用 countdown(2):
打印 2 → 调用 countdown(1):
打印 1 → 调用 countdown(0):
0<=0 → return(不再递归,开始"一层层退出来")
每调用一次,问题就"小一号",直到小到出口为止。这就是递归的运行轨迹。
换例加深:倒着数的另一种写法——让打印发生在递归之后
def countup(n):
if n <= 0:
return
countup(n - 1) # 先派分身
print(n) # 再打印
countup(3)
运行结果:
1
2
3
诶?顺序反过来了! 因为 print(n) 在递归调用之后,所以程序会先一路"递"到底,再一路"归"回来打印——打印发生在归来的路上。这个例子帮你理解"递"和"归"两个阶段:递归调用前是"去"的路上,之后是"回"的路上。
🐍"皮皮注:递归看起来像绕口令,但它本质就是'循环的另一种写法'。区别在于:循环是自己跑圈,递归是派分身去干活,分身再派分身……直到最小的分身把答案传回来。"
易错提醒: 出口一旦忘了,递归就会无限套娃直到 RecursionError。写完递归先问自己一句:"什么情况下它不再调用自己?"
18.2 递归三要素
皮皮给你总结,写递归必须凑齐三要素:
- 出口(基线条件):什么时候不再递归,直接返回答案。没有出口 = 无限套娃 = 崩溃。
- 递推(递归步骤):把问题变成"更小一号的同款问题"。
- 保证规模在缩小:每次递归,问题必须真的变小,否则永远到不了出口。
对照一个"错误示范"检查三要素:
def wrong(n):
if n <= 0: # ① 出口有
return
return wrong(n) # ② 递推有 ③ 但规模没变小!n 还是 n
这个函数出口写了,但 wrong(n) 每次还是传 n——问题根本没有变小,永远到不了出口,照样 RecursionError。三要素缺一不可。
💡 记住一句检查口诀:"有出口、能拆小、每次真变小。" 三个条件都满足,递归才安全。
18.3 经典例子:阶乘
阶乘:n! = n × (n-1) × (n-2) × ... × 1。
先看规律:
5! = 5 × 4 × 3 × 2 × 1- 但
4! = 4 × 3 × 2 × 1 - 所以
5! = 5 × 4!
发现没?5! 可以拆成 5 × 4!——一个大问题变成"乘一个更小的同款问题"。 这就是递归的入口。
写成代码:
def factorial(n):
if n <= 1: # 出口:1! 和 0! 都是 1
return 1
return n * factorial(n - 1) # 递推:n! = n × (n-1)!
print(factorial(5)) # 120
print(factorial(6)) # 720
运行结果:
120
720
逐行拆解:
- if n <= 1: return 1:出口。1! = 1、0! = 1,直接返回;
- return n * factorial(n - 1):递推。n! = n × (n-1)!,把 n! 变成"乘一个更小的阶乘";
- factorial(5):一路拆到 factorial(1),拿到 1,再一路乘回来。
追踪 factorial(5) 是怎么算的:
factorial(5)
= 5 * factorial(4)
= 5 * (4 * factorial(3))
= 5 * (4 * (3 * factorial(2)))
= 5 * (4 * (3 * (2 * factorial(1))))
= 5 * (4 * (3 * (2 * 1))) ← 出口,开始一层层往回乘
= 5 * (4 * (3 * 2))
= 5 * (4 * 6)
= 5 * 24
= 120
先一路"递"到出口,再一路"归"回来算出结果。 "递归"这个词就是这么来的:递出去,再归回来。
换例加深:把阶乘的出口改成 n == 0 行不行?
def factorial2(n):
if n == 0: # 只处理 n==0
return 1
return n * factorial2(n - 1)
factorial2(5) 也能算出 120,但 factorial2(0) 后你再调 factorial2(-1)…… 出口没拦住负数,又会 RecursionError。写出口时想想边界:负数和边界值会不会漏进来。
配套代码文件:code/ch18/factorial.py。
易错提醒: 递推那行必须 return。写成 n * factorial(n - 1) 忘加 return,结果就是 None——这就是翻车现场的坑 4。
18.4 经典例子:斐波那契
斐波那契数列:0, 1, 1, 2, 3, 5, 8, 13, ...,从第 3 项起,每一项 = 前两项之和。
规律:第 n 项 = 第 n-1 项 + 第 n-2 项。这又是一个"大问题拆成两个更小同款问题"的经典:
def fib(n):
if n <= 0:
return 0 # 出口1
if n == 1:
return 1 # 出口2
return fib(n - 1) + fib(n - 2) # 递推
for i in range(10):
print(fib(i), end=" ")
运行结果:
0 1 1 2 3 5 8 13 21 34
逐行拆解:
- if n <= 0: return 0:出口 1。第 0 项是 0;
- if n == 1: return 1:出口 2。第 1 项是 1;
- return fib(n - 1) + fib(n - 2):递推。第 n 项 = 前两项之和,一次拆成两个更小的同款问题;
- for i in range(10): print(fib(i), end=" "):循环打印前 10 项,end=" " 让它们在一行输出(空格分隔)。
斐波那契是"一拆二"的典型:每个问题分裂成两个小问题,两个又各自分裂……调用次数会指数级暴涨。
换例加深:用循环写同一个斐波那契
def fib_loop(n):
a, b = 0, 1
for _ in range(n):
a, b = b, a + b
return a
for i in range(10):
print(fib_loop(i), end=" ")
# 0 1 1 2 3 5 8 13 21 34
同一个结果,循环版快得多。 对比一下:递归版 fib(30) 可能卡顿,循环版瞬间出结果。这提醒你——递归漂亮,但要知道它的成本。
🐍"皮皮注:这个斐波那契的递归版虽然漂亮,但很慢——它在重复计算很多次(算 fib(10) 会调用 fib 数百次)。优化方式(缓存、循环)以后学,现在先感受递归的思想就够了。皮皮的话:帅,但别急着用。"
配套代码文件:code/ch18/fibonacci.py。
易错提醒: 斐波那契的出口要写两个——n<=0 和 n==1 都是边界,漏一个就会算错或无限递归。
18.5 递归 vs 循环:各有各的菜
能用循环解决的,递归都能解决;能用递归解决的,循环也大多能解决。 那怎么选?
| 循环 | 递归 | |
|---|---|---|
| 可读性 | 逻辑直白,好懂 | 数学味浓,有时更"像问题本身" |
| 性能 | 快(没有调用开销) | 慢(每层都要压栈) |
| 适用 | 大部分日常场景 | 树/分治类问题(如目录遍历、汉诺塔) |
什么时候该用递归? 当问题本身就长着"一棵树"的样子——每一层要处理的事一样,只是规模更小。比如:
- 遍历文件夹(文件夹里有子文件夹,子文件夹里还有……);
- 汉诺塔(见习题);
- 树的搜索、全排列。
这种问题用循环写,往往要自己维护一堆"待办清单";用递归写,三五行就完了。
皮皮的建议: 日常写代码,优先用循环。遇到"嵌套结构、每层都要做同样处理"的问题(遍历目录、汉诺塔),再考虑递归——这时候递归往往比循环简洁得多。
换例加深:两个版本加起来求和
# 循环版
def sum_loop(n):
total = 0
for i in range(1, n + 1):
total += i
return total
# 递归版
def sum_rec(n):
if n <= 0:
return 0
return n + sum_rec(n - 1)
print(sum_loop(100)) # 5050
print(sum_rec(100)) # 5050
结果一样,思路不同:循环版"从小到大一点点加",递归版"从 n 一路拆到 0 再一路加回来"。哪个都好,日常选循环版(更快更省内存)。
18.6 递归深度:套娃也有上限
还记得 18.1 那个没有出口的 countdown 吗?运行它,你不会"无限"跑下去,而是会报:
RecursionError: maximum recursion depth exceeded
原因: 每次递归调用,Python 都要在内存里记一层"现场",默认上限约 1000 层。超过就报 RecursionError(递归深度超限)。
所以:
- 忘写出口 → 无限递归 → RecursionError。这是递归最大的坑;
- 出口写太晚也一样(比如阶乘的出口
n<=1,传很大的 n 也会超限); - 真要用递归处理超大输入,可以调整上限(
sys.setrecursionlimit),但治标不治本——递归不适合超深的问题,这种时候回到循环或迭代才是正道。
逐行拆解一下报错信息:
RecursionError: maximum recursion depth exceeded
RecursionError:异常类型,表示"递归出问题了";maximum recursion depth exceeded:"超过了最大递归深度"——套娃套太多层,内存记不下了。
💡 看到这个报错,先别慌,按顺序排查:① 有没有出口?② 出口条件对不对?③ 每次递归问题有没有变小? 九成的情况是这三条之一。
【皮皮小课堂】本章要点
- 递归 = 函数调用自己,像俄罗斯套娃。
- 递归三要素:出口(何时停止)、递推(拆成更小同款问题)、规模递减(必须真的变小)。
- 阶乘:
n! = n × (n-1)!,出口n<=1。 - 斐波那契:
fib(n) = fib(n-1) + fib(n-2),出口 0 和 1。 - 递归调用前是"去"的路上,调用后是"回"的路上(影响打印顺序)。
- 递归 vs 循环:日常用循环;树形/分治问题用递归更清晰。
- 递归深度上限:约 1000 层,超限报
RecursionError。 - 忘写出口 = 无限递归,写完先检查出口。
【翻车现场】本章的坑
坑 1:忘了出口 → RecursionError
def forever(n):
return forever(n + 1) # ❌ 没有出口
forever(1) # RecursionError
写完递归,第一件事:检查出口。 没有出口就是无限套娃。
坑 2:出口写对,但规模没变小
def bad(n):
if n == 0:
return 0
return bad(n) # ❌ n 还是 n,没变小,永远到不了出口
递推那一步必须让问题变小。"有出口"和"能到达出口"是两回事。
坑 3:把递归当循环用,性能爆炸
斐波那契递归版在大数下会慢到怀疑人生。fib(35) 就要调用几十万次。知道它慢,需要性能时就用循环(或者用后面学的"缓存"优化)。
坑 4:return 写漏
def factorial(n):
if n <= 1:
return 1
n * factorial(n - 1) # ❌ 忘了 return,返回 None
factorial(n-1) 的结果必须 return 出去,否则上一层拿到的是 None,再乘 n 直接 TypeError: unsupported operand type(s) for *: 'int' and 'NoneType'。
坑 5:出口条件挡不住边界值
def factorial(n):
if n == 1: # 只挡 n==1
return 1
return n * factorial(n - 1)
factorial(0) # ❌ n 从 0 → -1 → -2 ...,永远到不了 1 → RecursionError
出口要覆盖边界。 0! 也是 1,所以写成 if n <= 1: return 1 更稳——<= 把 0、负数都挡在门外。
坑 6:打印位置放错,结果顺序全反
def countdown(n):
if n <= 0:
return
countdown(n - 1) # ❌ 想倒着数,却把递归放前面了
print(n)
递归调用前打印 = "去"的路上打印(递减);递归调用后打印 = "回"的路上打印(递增)。 想清楚你要的是哪种,再决定 print 放哪。实在分不清,就画一张"递/归"轨迹图。
【本章习题】
一、选择题
1. (★) 一个递归函数没有出口会发生什么?
- A. 无限运行但没事
- B. 报错
RecursionError: maximum recursion depth exceeded - C. 正常结束
- D. 电脑自动关机
2. (★★) factorial(4) 的结果是?
- A.
4 - B.
10 - C.
24 - D.
64
3. (★★) 递归三要素不包括下列哪一项?
- A. 出口(基线条件)
- B. 递推(拆成更小的同款问题)
- C. 保证问题规模在缩小
- D. 使用
global关键字
4. (★★) 运行 sum_rec(3)(sum_rec 见下面代码),输出结果是?
def sum_rec(n):
if n <= 0:
return 0
return n + sum_rec(n - 1)
print(sum_rec(3))
- A.
3 - B.
6 - C.
1 - D.
RecursionError
5. (★★ 多选) 关于递归,下列说法正确的是?
- A. 递归是函数调用自己
- B. 递归必须有出口,否则会无限递归
- C. 递归一定能比循环快
- D. 递归每调用一次,问题应该变小
二、判断题
1. (★) 1! 和 0! 在递归阶乘里都作为出口,返回 1。( )
2. (★★) 斐波那契数列的第 3 项(从 0 开始数,即 fib(3))是 2。( )
3. (★★) 所有能用递归解决的问题,都能用循环解决。( )
4. (★★) 把 print 放在递归调用之后,打印顺序会反过来(先打印最小的)。( )
三、代码纠错题
1. (★★) 下面递归想算阶乘,但一运行就报错,请指出问题并改正:
def factorial(n):
return n * factorial(n - 1)
2. (★★) 下面递归想算 1+2+...+n,但结果老是 None,请指出问题并改正:
def sum_rec(n):
if n <= 0:
return 0
n + sum_rec(n - 1) # 结果没 return 出去
四、编程实战题
1. (基础 ★) 用递归写一个函数 sum_to(n),计算 1 + 2 + ... + n 的和。提示:sum_to(n) = n + sum_to(n-1),出口 n <= 0 时返回 0。
2. (基础 ★★) 用递归写一个函数 reverse_str(s),返回字符串的反转。提示:reverse_str(s) = s[-1] + reverse_str(s[:-1]),出口:空串返回空串。
3. (基础 ★★) 用递归写一个函数 count_digits(n),返回正整数 n 有几位数字。提示:count_digits(n) = 1 + count_digits(n // 10),出口:n 小于 10 时返回 1。
4. (挑战 ★★★) 汉诺塔:有三根柱子 A、B、C,A 柱上从上到下叠着 n 个盘子,要求把全部盘子移到 C 柱,规则:一次只能动一个盘子,大盘子永远不能压在小盘子上面。写递归函数 hanoi(n, a, b, c) 打印移动步骤(提示:先把上面 n-1 个盘子经 C 移到 B,再把第 n 个移到 C,最后把 B 上的 n-1 个经 A 移到 C)。
【参考答案与解析】
一、选择题
1. 答案:B
没有出口会无限递归,直到超过深度上限报 RecursionError。
2. 答案:C
4! = 4×3×2×1 = 24。
3. 答案:D
递归三要素是出口、递推、规模递减。global 和作用域有关,不是递归的要素。
4. 答案:B
sum_rec(3) = 3 + sum_rec(2) = 3 + (2 + sum_rec(1)) = 3 + (2 + (1 + sum_rec(0))) = 3 + 2 + 1 + 0 = 6。注意出口返回的是 0,不是 1。
5. 答案:A、B、D
A 对:B 对:没出口会无限递归; C 错:递归往往更慢(有调用开销); D 对:每次要变小才能到达出口。
二、判断题
1. 正确(√)。0! = 1、1! = 1,都返回 1。
2. 正确(√)。fib:0,1,1,2,3,5…所以 fib(3) = 2。
3. 错误(×)。实际上几乎所有递归都能改成循环,但有些问题(如树形结构)用循环实现会非常别扭。这话"所有"太绝对,以理解为准——能用循环的优先用循环。
4. 正确(√)。递归调用前的代码在"去"的路上执行,之后的在"回"的路上执行。print 放递归后,先到出口,再一层层打印,顺序自然反过来。
三、代码纠错题
1. 解析: 没有出口,factorial(n) 无限调用自己直到 RecursionError。改正:加出口:
def factorial(n):
if n <= 1: # 出口
return 1
return n * factorial(n - 1)
2. 解析: n + sum_rec(n - 1) 算出了结果,但没有 return,函数返回 None。改正:
def sum_rec(n):
if n <= 0:
return 0
return n + sum_rec(n - 1)
print(sum_rec(3)) # 6
检查递归的每个分支,看是不是都有 return 把结果交出去。
四、编程实战题
1. 参考代码:
def sum_to(n):
if n <= 0:
return 0
return n + sum_to(n - 1)
print(sum_to(100)) # 5050
2. 参考代码:
def reverse_str(s):
if s == "":
return ""
return s[-1] + reverse_str(s[:-1])
print(reverse_str("Python")) # nohtyP
💡 对比第 5 章的
s[::-1],递归版慢得多,但它展示了"同一个问题缩小规模"的思考方式。
3. 参考代码:
def count_digits(n):
if n < 10:
return 1
return 1 + count_digits(n // 10)
print(count_digits(5)) # 1
print(count_digits(12345)) # 5
print(count_digits(20260810)) # 8
拆解: count_digits(12345) = 1 + count_digits(1234) = 1 + 1 + count_digits(123) = ...。每次 n // 10 去掉最后一位,直到只剩一位数(小于 10)返回 1。// 是整除,还记得第 4 章学的吗?
4. 参考代码:
def hanoi(n, a, b, c):
if n == 1:
print(f"{a} -> {c}")
return
hanoi(n - 1, a, c, b) # 上面 n-1 个:经 C 移到 B
print(f"{a} -> {c}") # 第 n 个:直接到 C
hanoi(n - 1, b, a, c) # B 上的 n-1 个:经 A 移到 C
hanoi(3, "A", "B", "C")
运行结果:
A -> C
A -> B
C -> B
A -> C
B -> A
B -> C
A -> C
逐行拆解:
- if n == 1: print(f"{a} -> {c}"):出口。只剩一个盘子,直接从 a 挪到 c;
- hanoi(n - 1, a, c, b):把上面 n-1 个盘子"暂时"挪到 b(借道 c);
- print(f"{a} -> {c}"):把最底下的大盘子挪到 c;
- hanoi(n - 1, b, a, c):再把 b 上那 n-1 个挪回 c(借道 a)。
🐍"皮皮注:汉诺塔是递归的'巅峰演出'——三行逻辑,就能解决一个看起来超级复杂的问题。这题看不懂很正常,先照抄运行看结果,感受'问题规模缩小'的威力,别急着背。"
📖 函数部分毕业。下一部分,我们要让程序和外界打交道:文件读写、异常处理、模块。