推荐卡连成一条链：A 拉了 B，B 又拉了 C，后面还有。Maya 想知道每条链有多深，而不是一个个手数。递归在哪里停下来？
递归函数会用更小的输入调用自己。每个递归都需要一个能停止调用的基线条件，而且每一步都必须朝基线靠近。满足这两个条件时，递归可以把嵌套问题表达得更短。 你还会跟踪调用栈、摊平嵌套列表，并缓存重复分支。
先写基线条件
基线条件是不用再调用就能回答的最小输入。factorial(1) 会立刻返回 1。没有基线条件，函数会一直调用自己，直到 Python 抛出 RecursionError。
def factorial(n):
if n <= 1:
return 1
return n * factorial(n - 1)
print(factorial(5))一次递归调用
两次调用，更小的输入
斐波那契天然是两路递归：fib(n) 依赖 fib(n - 1) 和 fib(n - 2)。前两个值是基线条件。画出小 n 的调用树，就能看出这个版本为什么会重复计算。
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(6))分叉的递归
遍历嵌套列表
递归列表函数先处理第一个元素，再把剩下的列表交给更小的调用。空列表是基线条件。这个模式不只适用于平铺列表，也适用于树和嵌套结构。
def total(items):
if not items:
return 0
return items[0] + total(items[1:])
print(total([1, 2, 3]))不断缩短的列表
调用栈会反向展开
每次递归调用都会暂停它的调用者。基线条件先返回，然后每一层调用者恢复执行，组合返回值。向下和向上各打印一次，就能看清最终结果为什么是从里往外构建的。
def walk(n):
if n == 0:
print("base")
return 0
print("enter", n)
result = walk(n - 1) + n
print("leave", n, "result", result)
return result
print("total", walk(3))向下进入，向上组合
返回新结构，不要依赖全局变量
递归函数应该返回自己的部分结果。全局累加器会让多次调用互相干扰，也难以测试。摊平嵌套列表时，把第一个元素的结果和剩余部分的结果组合起来。
def flatten(items):
if not items:
return []
first, *rest = items
if isinstance(first, list):
return flatten(first) + flatten(rest)
return [first] + flatten(rest)
print(flatten([1, [2, [3, 4]], 5]))组合返回值，而不是共享状态
缓存重复分支
朴素斐波那契会重复计算相同的子问题。lru_cache 按参数保存结果，对这种形状能把指数级工作变成线性级。只有纯函数、且参数可哈希时，缓存才是安全的。
from functools import lru_cache
@lru_cache(maxsize=None)
def fib(n):
if n < 2:
return n
return fib(n - 1) + fib(n - 2)
print(fib(30))
print(fib.cache_info().hits > 0)缓存纯函数的子问题
本课要点
- 每个递归函数都需要基线条件。
- 每次调用都必须使用更小或更简单的输入。
- 递归调用返回的值由调用者继续组合。
- 递归太深或重复太多时，循环可能更清楚。
- 递归从内向外返回；记忆化能去掉重复分支。
常见错误
- 忘记基线条件，导致 RecursionError。
- 用同样的输入调用函数，而不是缩小输入。
- 忽略分叉递归中的重复计算。
- 缓存会读取变化中的全局状态或修改输入的函数。
写一个递归函数，把列表中的数字相加，然后打印 [2, 4, 6] 的结果。
动手试试
改改变量、先预测输出，再运行代码。第一次点击“运行代码”时会下载 Python 运行时，可能需要几秒钟。
练习本课
12 道题，作答后立即看到解释。