递归

第 20 课，共 31 课 · 第 3 部分 · 函数 · 约 20 分钟

函数可以调用别的函数，也可以调用它自己，这就是递归。听着像个花招，其实一个问题里面要是藏着一个更小的同样的问题，用递归来解就很自然。从 3 开始倒数，就是「说 3，再从 2 开始倒数」：

main.py

1def countdown(n):2    if n == 0:3        print("灯亮了！")4    else:5        print(n)6        countdown(n - 1)7 8countdown(3)

输出

3
2
1
灯亮了！

每个递归函数都有两部分：

部分	做什么	在 `countdown` 里
终止条件	简单到可以直接回答，不再往下调用	`n == 0`：显示一句，结束
递归的一步	做一点事，再拿一个更小的问题调用自己	显示 `n`，再 `countdown(n - 1)`

每调用一次，问题就小一点，早晚会到终止条件，调用就停下来了。

阶乘

5 的阶乘写作 5!，是 5 × 4 × 3 × 2 × 1 = 120。换个角度看：5! 是 5 × 4!，4! 是 4 × 3!，一直到 1! = 1。这已经是一个递归函数了：

main.py

1def factorial(n):2    if n <= 1:3        return 14    return n * factorial(n - 1)5 6print(factorial(4))7print(factorial(5))

输出

24
120

factorial(4) 没法马上算完：它要等 factorial(3)，factorial(3) 等 factorial(2)，factorial(2) 等 factorial(1)。factorial(1) 返回 1 以后，等着的那几层再倒着一层一层算完：2 × 1、3 × 2、4 × 6。

小技巧： 这段代码点单步看看。能看到调用一层一层叠上去，直到 n 是 1，再一层一层回来，每一层都有自己的 n。

看清每一层调用

每次调用都有自己的局部变量，这一层的 n 和下一层的 n 是两个不同的变量。想看清调用怎么一层套一层，可以给函数多加一个参数，记住现在是第几层，显示的时候按层数缩进：

main.py

1def factorial(n, depth=0):2    pad = "    " * depth3    print(f"{pad}factorial({n})")4    if n <= 1:5        print(f"{pad}返回 1")6        return 17    result = n * factorial(n - 1, depth + 1)8    print(f"{pad}返回 {result}")9    return result10 11factorial(3)

输出

factorial(3)
    factorial(2)
        factorial(1)
        返回 1
    返回 2
返回 6

Python 用一个栈记着那些开始了、还没结束的调用。每次新的调用放到最上面；每次 return 把最上面那个拿掉，把值交给下面那一层。小游戏无限套娃玩的就是这个：Wick 一层一层地分身，再一层一层地回来。

先猜一猜

这段会显示什么？

1def show(n):2    if n == 0:3        return4    show(n - 1)5    print(n)6 7show(3)

print(n) 在递归调用的后面，所以每一层都要等更深的那几层全做完。show(1) 先显示，然后是 show(2)，最后是 show(3)。show(0) 什么都不显示就返回了。

输出

字符串和列表上的递归

一个字符串就是第一个字加上剩下的部分。所以倒过来的做法是：先把剩下的倒过来，再把第一个字放到最后。空字符串是终止条件。

main.py

1def reverse(text):2    if text == "":3        return ""4    return reverse(text[1:]) + text[0]5 6print(reverse("点灯人"))7print(reverse("Wick"))

输出

人灯点
kciW

列表也一样：第一项，加上剩下的列表。空列表是终止条件。

main.py

1def total(items):2    if not items:3        return 04    return items[0] + total(items[1:])5 6def longest(words):7    if len(words) == 1:8        return words[0]9    rest = longest(words[1:])10    return words[0] if len(words[0]) >= len(rest) else rest11 12print(total([3, 8, 2, 6]))13print(longest(["矿石", "小镇仓库", "灯"]))

输出

19
小镇仓库

函数	终止条件	递归的一步
`reverse`	`""` 得到 `""`	`reverse(text[1:]) + text[0]`
`total`	`[]` 得到 `0`	`items[0] + total(items[1:])`
`longest`	只有一个词，就是这个词	`words[0]` 和 `longest(words[1:])` 里长的那个

这种平的列表，用循环或者 sum() 更简单。递归真正好用的，是下面这种数据。

嵌套的数据

仓库把矿石装在箱子里，有的箱子里还套着小箱子，套几层都有可能。光靠一个简单的循环不好对付「套几层都有可能」，递归可以：每样东西，是数字就加上；是箱子，就用同样的办法把这个箱子数一遍。

main.py

1def count_ore(crate):2    total = 03    for item in crate:4        if isinstance(item, list):5            total += count_ore(item)6        else:7            total += item8    return total9 10warehouse = [4, [2, 3], [1, [5, 6]], 7]11print(count_ore(warehouse))

输出

isinstance(item, list) 问的是「item 是不是列表」，得到 True 或 False（第 27 课再细讲）。这里的终止条件不是开头的一个 if，而是里面不再有箱子的箱子：循环走完了，也没再调用 count_ore。

忘了终止条件

没有终止条件，就没有什么能让调用停下来。这个 total 本来要算 3 + 2 + 1，可是到了 0 也不停：

main.py

1def total(n):2    return n + total(n - 1)3 4print(total(3))

输出

Traceback (most recent call last):
  File "main.py", line 4, in <module>
    print(total(3))
  File "main.py", line 2, in total
    return n + total(n - 1)
  File "main.py", line 2, in total
    return n + total(n - 1)
  File "main.py", line 2, in total
    return n + total(n - 1)
  [Previous line repeated 297 more times]
RecursionError: maximum recursion depth exceeded

发生了什么： 函数一直调用自己，停不下来。

每一层都在等下一层，调用的栈越叠越高。层数太多时 Python 会停下来，报 RecursionError。标准的 Python 默认最多 1000 层。看到这个报错，查两件事：有没有终止条件？每次调用是不是真的离它更近了？

先猜一猜

会怎么样？

1def countdown(n):2    if n == 0:3        print("完成")4        return5    countdown(n - 2)6 7countdown(5)

5、3、1、-1、-3……从奇数开始每次减 2，正好跳过了 0，永远到不了终止条件。写成 if n <= 0: 更稳妥。

输出

斐波那契的重复计算

斐波那契数列 0、1、1、2、3、5、8、13……里，每个数是前两个数的和。照着这句话写，就是一个有两个递归调用的函数。用一个全局变量数一数它一共调用了多少次：

main.py

1calls = 02 3def fib(n):4    global calls5    calls += 16    if n < 2:7        return n8    return fib(n - 1) + fib(n - 2)9 10for n in [5, 10, 15]:11    calls = 012    result = fib(n)13    print(f"fib({n}) = {result}，调用了 {calls} 次")

输出

fib(5) = 5，调用了 15 次
fib(10) = 55，调用了 177 次
fib(15) = 610，调用了 1973 次

调用次数比 n 涨得快得多。原因是重复计算：fib(5) 调用 fib(4) 和 fib(3)，可 fib(4) 里又调用了一次 fib(3)，每个 fib(3) 又把 fib(2) 再算一遍，越往下越多。换成循环，只记住最后两个数，每一步只算一次：

main.py

1def fib(n):2    a, b = 0, 13    for step in range(n):4        a, b = b, a + b5    return a6 7print(fib(15))8print(fib(50))

输出

610
12586269025

递归还是循环

递归能做的，循环都能做，反过来也一样。看问题是什么样子来挑：

用	什么时候	例子
递归	数据是嵌套的，或者问题能拆成几个更小的同样的问题	箱子套箱子、文件夹、家谱、解谜
循环	一个接一个地处理	求和、计数、列表、阶乘
循环	可能要几千层那么深	从 1 加到 5000

最后一行要紧，因为每一层递归在返回之前都占着栈上的一个位置：

main.py

1def sum_to(n):2    if n == 0:3        return 04    return n + sum_to(n - 1)5 6def sum_to_loop(n):7    total = 08    for i in range(1, n + 1):9        total += i10    return total11 12print(sum_to(100))13print(sum_to_loop(5000))14print(sum_to(5000))

输出

5050
12502500
Traceback (most recent call last):
  File "main.py", line 14, in <module>
    print(sum_to(5000))
  File "main.py", line 4, in sum_to
    return n + sum_to(n - 1)
  File "main.py", line 4, in sum_to
    return n + sum_to(n - 1)
  File "main.py", line 4, in sum_to
    return n + sum_to(n - 1)
  [Previous line repeated 297 more times]
RecursionError: maximum recursion depth exceeded

发生了什么： 函数一直调用自己，停不下来。

最后一行超过了 Python 对递归深度的限制，引发 RecursionError。循环没有这个限制。

练一练

写好代码，点检查。提示随便看，实在想不出来再看答案。每道题都用递归来做，先想好终止条件。

练习 1

乘方

把 power(base, exp) 写完，让它调用自己，算出 base 的 exp 次方。不要用 **。

要显示

1024
81

exercise1.py

1def power(base, exp):2    return 03 4print(power(2, 10))5print(power(3, 4))

输出

点「运行」或按 Ctrl+Enter

练习 2

数一个字

把 count_char(text, ch) 写完，用递归（不用 .count()）返回 ch 在 text 里出现了几次。

要显示

3
0

exercise2.py

1def count_char(text, ch):2    return 03 4print(count_char("灯灯不灭灯", "灯"))5print(count_char("矿石", "灯"))

输出

点「运行」或按 Ctrl+Enter

练习 3

拆箱子

把 flatten(crate) 写完，不管箱子套了几层，都返回一个平的列表，按顺序放着所有的数。

要显示

[1, 2, 3, 4, 5]

exercise3.py

1def flatten(crate):2    result = []3    for item in crate:4        result.append(item)5    return result6 7print(flatten([1, [2, 3], [[4], 5]]))

输出

点「运行」或按 Ctrl+Enter

这一课学会了

递归函数拿一个更小的问题调用自己，直到遇到能直接回答的终止条件。
每次调用都有自己的局部变量；没做完的调用在栈上等着，倒着一层一层做完。
字符串和列表拆成「第一项 + 剩下的」；嵌套的数据拆成「这一层 + 里面的几层」。
没有终止条件，或者永远到不了终止条件，最后会报 RecursionError。
递归可能重复计算（比如 fib），也不能太深；简单的一步一步的事，循环往往更好。