函数 · 让代码长成模块

第18章 套娃大法

递归

第 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 递归三要素

皮皮给你总结,写递归必须凑齐三要素:

  1. 出口(基线条件):什么时候不再递归,直接返回答案。没有出口 = 无限套娃 = 崩溃。
  2. 递推(递归步骤):把问题变成"更小一号的同款问题"。
  3. 保证规模在缩小:每次递归,问题必须真的变小,否则永远到不了出口。

对照一个"错误示范"检查三要素:

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!——一个大问题变成"乘一个更小的同款问题"。 这就是递归的入口。

写成代码:

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: maximum recursion depth exceeded

💡 看到这个报错,先别慌,按顺序排查:① 有没有出口?② 出口条件对不对?③ 每次递归问题有没有变小? 九成的情况是这三条之一。


【皮皮小课堂】本章要点


【翻车现场】本章的坑

坑 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. (★) 一个递归函数没有出口会发生什么?

2. (★★) factorial(4) 的结果是?

3. (★★) 递归三要素不包括下列哪一项?

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))

5. (★★ 多选) 关于递归,下列说法正确的是?

二、判断题

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)。

🐍"皮皮注:汉诺塔是递归的'巅峰演出'——三行逻辑,就能解决一个看起来超级复杂的问题。这题看不懂很正常,先照抄运行看结果,感受'问题规模缩小'的威力,别急着背。"


📖 函数部分毕业。下一部分,我们要让程序和外界打交道:文件读写、异常处理、模块。

📦 本章配套代码

运行方式:命令行进入目录后执行 py 文件名.py(Windows)或 python3 文件名.py(Mac/Linux)