高阶函数与递归

写三个函数：求 1 + 2 + … + n，求 1² + 2² + … + n²，求一个收敛到 π 的级数前 n 项之和。写完你会发现三段代码几乎一模一样，只有”每一项怎么算”那一处不同。能不能只写一次循环，把”怎么算一项”作为参数传进去？这一篇从这个问题出发：函数既然是值，就可以当参数、当返回值；然后看函数调用自己会发生什么。两条线最后在记忆化那里汇合。

前置：函数与环境模型

把函数当参数

三个求和函数共同的骨架是：从 k = 1 到 n 累加 term(k)。把 term 变成参数：

def summation(n, term):
    total, k = 0, 1
    while k <= n:
        total, k = total + term(k), k + 1
    return total
print(summation(5, lambda k: k),
      summation(5, lambda k: k*k),
      summation(100, lambda k: 8 / ((4*k-3)*(4*k-1))))

15 55 3.1365926848388144

第三项是 8/(1·3) + 8/(5·7) + 8/(9·11) + …，加到第 100 项已经接近 π。三个问题现在共用一份循环逻辑，各自只提供一个一行的函数。

summation 这种接收函数作为参数、或者返回函数的函数叫高阶函数（higher-order function）。它之所以能成立，是因为在 Python 里函数和数字一样是值：可以绑定到名字、放进列表、传给别的函数。summation 的形参 term 在调用时被绑定到一个函数对象，函数体里 term(k) 就是对这个对象的普通调用，环境模型一点没变。

高阶函数的意义在于抽象出”做法”。普通函数把”对哪个数做”抽成参数；高阶函数更进一步，把”做什么”也抽成参数。一旦发现几段代码结构相同、只有某个操作不同，就该想到把那个操作提成函数参数。Python 内置的 map、filter、sorted(key=...) 都是这种模式。比如 sorted(words, key=len) 里，排序算法本身是固定的，“按什么比较”由调用者传进来的函数决定；同一个排序函数因此能按长度、按字母、按任意规则排序，而不用为每种规则各写一个排序。

lambda k: k*k 是 lambda 表达式：它求值为一个没有名字的函数，lambda 形参: 返回表达式。它和 def 的区别只有两点：lambda 是表达式，可以直接写在参数位置；函数体只能是一个表达式，不能有语句。它创建的函数对象同样记下定义时的父帧，所以环境模型对它完全适用。

停一下，检查理解单选

summation(3, lambda k: k ** 3) 的值是多少？

143627报错，因为 lambda 不能当参数传

检查答案

把函数当返回值：闭包

函数既然能当参数，也就能当返回值。下面的 make_adder 返回一个”加 n”的函数：

def make_adder(n):
    def adder(k):
        return n + k
    return adder
add3 = make_adder(3)
print(add3(4), add3.__closure__[0].cell_contents)

7 3

用环境模型一步步走：

1. 调用 make_adder(3)，新建帧 f1，父帧 Global，n 绑定到 3。
2. 在 f1 里执行 def adder：创建函数对象，它的父帧是 f1，因为它是在 f1 里定义的。
3. 返回这个函数对象，在 Global 里绑定为 add3。
4. 调用 add3(4)，新建帧 f2，k 绑定到 4。f2 的父帧取自函数对象，也就是 f1。
5. 函数体找 n：f2 没有，去 f1，找到 3。返回 7。

第 4 步是关键：make_adder 早就返回了，但它的帧 f1 没有消失，因为 adder 函数对象还引用着它。一个函数连同它定义时的环境，合起来叫闭包（closure）。__closure__[0].cell_contents 让我们直接看到闭包里存着的 n。

这就是上一篇”父帧 = 定义时的帧”这条规则真正的用武之地。如果规则是”父帧 = 调用者的帧”，add3(4) 在全局被调用，就找不到 n，闭包根本不可能存在。

返回函数的函数可以拿来组合函数：

def compose(f, g):
    return lambda x: f(g(x))
print(compose(lambda x: x*x, add3)(2))

25

compose(square, add3) 返回一个新函数，它先加 3 再平方。每次调用 make_adder 都会新开一个帧，所以 make_adder(3) 和 make_adder(10) 返回的两个函数各自带着自己的 n，互不影响。换个角度看，闭包是”一段代码 + 一份私有数据”，这已经是对象的雏形：数据藏在帧里，外界只能通过调用这个函数间接使用它。数据抽象与对象 会沿着这条线走下去，先用闭包表示数据，再引出可以修改的状态和类。

compose(...)(2) 这种连着两对括号的写法初看奇怪，其实就是”先求值操作符 compose(...)，得到一个函数，再把它应用到 2”，调用表达式的规则一点没变。

停一下，检查理解单选

add3 = make_adder(3) 执行完之后，make_adder 的那次调用帧（里面 n 绑定为 3）会怎样？

函数返回后立即销毁，add3 内部拷贝了一份 n 的值继续存在，因为 adder 函数对象把它当作父帧引用着被合并进全局帧，所以全局也能访问 n每次调用 add3 时重新执行一遍 make_adder 来创建

检查答案

Currying 与装饰器

既然函数可以返回函数，任何多参数函数都能改写成一串单参数函数。这叫 currying（以逻辑学家 Haskell Curry 命名）：

def curry2(f):
    return lambda x: lambda y: f(x, y)
from operator import add
print(curry2(add)(10)(5))
pow_of = curry2(pow)(2)
print([pow_of(k) for k in range(6)])

15
[1, 2, 4, 8, 16, 32]

curry2(pow)(2) 把 pow 的第一个参数固定成 2，得到”2 的几次方”这个新函数。固定一部分参数、留下其余参数，在很多场合比把所有参数一次给齐更方便，比如要把函数传给只接受单参数函数的 map。标准库 functools.partial 做的是同一件事。反过来，把一串单参数函数还原成多参数函数也很容易：lambda x, y: g(x)(y)。两种形式可以互相转换，说明它们表达的计算能力相同，选哪种只看哪种用起来顺手。

另一个常见的模式是包装：接收一个函数，返回一个行为增强了的同名函数。Python 为此提供了 @ 语法：

def trace(fn):
    def wrapped(x):
        print('->', fn.__name__, x)
        return fn(x)
    return wrapped
@trace
def triple(x):
    return 3 * x
print(triple(4))
print(triple.__name__)

-> triple 4
12
wrapped

@trace 放在 def triple 上面，完全等价于定义完之后再执行 triple = trace(triple)。这就是**装饰器（decorator）**的全部原理：它只是语法糖，背后是一个高阶函数加一次重新绑定。wrapped 是闭包，记住了原来的 fn；全局的名字 triple 则被改绑到 wrapped 上。

最后一行 triple.__name__ 显示的是 wrapped，说明调用者手里的已经不是原函数了。这会让调试信息和文档变得混乱，工程上用 functools.wraps 修复，带参数的装饰器、类装饰器等用法见 Python 对象模型。

停一下，检查理解单选

下面哪种写法和 @trace 加在 def triple(x): ... 上面效果完全相同？

在 triple 的函数体第一行调用 trace(triple)正常定义 triple，然后执行 triple = trace(triple)正常定义 triple，然后执行 trace(triple)把 trace 的函数体复制进 triple

检查答案

闭包的一个陷阱：绑定的是名字，不是值

闭包记住的是帧里的名字，而不是创建时那一刻的值。在循环里创建函数时，这一点会产生意外：

fs = [lambda: i for i in range(3)]
print([f() for f in fs])
fs = [lambda i=i: i for i in range(3)]
print([f() for f in fs])

[2, 2, 2]
[0, 1, 2]

三个 lambda 都在同一个帧里创建（列表推导式自己的那个帧），它们的父帧相同，里面只有一个名字 i。调用它们时循环已经结束，i 停在 2，三个函数沿父帧找到的都是同一个 i。

修正的写法 lambda i=i: i 利用了默认参数在定义时求值的性质：每个 lambda 创建时就把当时的 i 存成自己的默认值，调用时绑定在自己的新帧里。另一种修法是写一个工厂函数 make(i) 返回 lambda，每次调用工厂都开一个新帧，每个 lambda 各有一个父帧。两种修法本质相同：让每个函数有自己的绑定，而不是共享一个。

停一下，检查理解单选

fs = [lambda: i for i in range(3)] 之后 fs[0]() 返回 2，根本原因是什么？

lambda 在创建时复制了 i 的值，但复制的是最后一个三个 lambda 共享同一个父帧，调用时才去查 i，而那时 i 已经是 2列表推导式把三个 lambda 合并成了一个函数Python 的 lambda 不支持闭包，只能看到全局变量

检查答案

递归：相信更小的那个问题

换一个方向。一个函数能不能在函数体里调用自己？

def fact(n):
    if n == 0:
        return 1
    return n * fact(n - 1)
print(fact(5))

120

按环境模型，fact(5) 开一个帧，n 是 5；它调用 fact(4)，再开一个新帧，n 是 4……一直到 fact(0) 返回 1，然后一层层乘回来。每个帧都有自己的 n，互不覆盖，这正是上一篇”每次调用一个新帧”带来的。递归在机制上没有任何新东西。

新东西在怎么想。逐层追踪 fact(5) 的五个帧很累，追踪 fact(1000) 不可能。CS61A 推荐的思路叫信任跳跃（recursive leap of faith）：写 fact(n) 时，假设 fact(n-1) 已经正确，只检查两件事：

1. **基本情况（base case）**对不对：fact(0) 应该是 1。
2. 递归情况能不能用更小问题的答案拼出当前答案：n! = n × (n-1)!，成立。

再加上”每次递归参数都在向基本情况靠近”，正确性就成立了，这和数学归纳法是同一个结构（归纳法本身见 离散数学）。递归函数的代码结构和问题的定义结构一模一样，这是它比循环更好读的原因。

递归和循环能表达同样的计算，但它们记录”还剩什么没做”的方式不同。给 fact 加一行打印，再写一个循环版对比：

def fact_iter(n):
    total, k = 1, 1
    while k <= n:
        total, k = total * k, k + 1
    return total
def fact(n):
    print('  ' * (3 - n) + f'fact({n})')
    if n == 0:
        return 1
    return n * fact(n - 1)
print(fact(3), fact_iter(3), fact_iter(5000) > 10**16000)

fact(3)
  fact(2)
    fact(1)
      fact(0)
6 6 True

缩进一层就是多一个还没返回的帧。递归版在 fact(0) 返回之前，fact(3)、fact(2)、fact(1) 的帧都挂着，每个都在等”拿到下一层结果后乘上自己的 n”，待完成的乘法存在帧里。循环版把这份信息显式地存在 total 和 k 两个名字里，始终只有一个帧，所以 fact_iter(5000) 毫无压力。把递归改写成循环，本质上就是想清楚”需要记住哪些状态”，然后自己用变量记下来。第四篇讲尾递归时会看到，如果递归调用之后不再有待做的事，解释器可以自动完成这种改写。

递归调用不一定是自己调用自己。两个函数互相调用叫互递归（mutual recursion）：

def is_even(n): return True if n == 0 else is_odd(n-1)
def is_odd(n): return False if n == 0 else is_even(n-1)
print(is_even(10), is_odd(7))

True True

每个帧都要占空间，所以递归深度是有限的：

import sys; print(sys.getrecursionlimit())
try: fact(5000)
except RecursionError as e: print('RecursionError:', e)

1000
RecursionError: maximum recursion depth exceeded in comparison

CPython 默认最多约 1000 层。fact(5000) 要同时存在 5000 个帧，超限报错。基本情况写错（比如写成 n == 1 却调用 fact(0)）时也会一路递归到这个上限。有些语言能让特定形式的递归不占新空间，第四篇的尾递归会讲到；帧在机器层面怎么摆在栈上，见 机器级程序。

停一下，检查理解多选

写一个递归函数时，"信任跳跃"要求你检查哪些事？

基本情况返回的值正确假设更小的递归调用正确时，能组合出当前问题的正确答案每次递归调用的参数都在向基本情况靠近手动展开所有递归层，确认每一层的中间结果

检查答案

树递归：一次调用分出好几条路

fact 每次只调用自己一次，调用过程是一条链。如果一次调用里有两个递归调用，调用过程就会长成一棵树，这叫树递归（tree recursion）。

CS61A 的经典例子是划分计数：把正整数 n 写成若干个不超过 m 的正整数之和（不计顺序），有几种写法？比如 n = 6, m = 4：4+2、4+1+1、3+3、3+2+1、3+1+1+1、2+2+2、2+2+1+1、2+1+1+1+1、1+1+1+1+1+1，共 9 种。

直接枚举很难写，但可以把所有写法分成不相交的两类：至少用了一个 m 的，和完全不用 m 的。

• 至少用一个 m：先拿掉一个 m，剩下的 n - m 仍然可以用不超过 m 的数来拆，有 count_partitions(n - m, m) 种。
• 完全不用 m：等价于用不超过 m - 1 的数拆 n，有 count_partitions(n, m - 1) 种。

def count_partitions(n, m):
    if n == 0: return 1
    if n < 0 or m == 0: return 0
    return count_partitions(n - m, m) + count_partitions(n, m - 1)
print(count_partitions(6, 4), count_partitions(10, 10))

9 42

基本情况要仔细想：n == 0 说明恰好拆完，是一种合法写法，返回 1；n < 0 是拆过头了，m == 0 是没有可用的数了，都返回 0。树递归的思考模式就是这样：找一个能把问题分成几类的选择，每类是一个更小的同类问题，答案是各类之和。

汉诺塔是另一个例子。要把 n 个盘子从 A 移到 C，借助 B：先把上面 n-1 个移到 B，再把最大的移到 C，再把 n-1 个从 B 移到 C。

def hanoi(n, src, dst, via):
    if n == 1:
        print(f'move {src}->{dst}'); return 1
    return hanoi(n-1, src, via, dst) + hanoi(1, src, dst, via) + hanoi(n-1, via, dst, src)
print(hanoi(3, 'A', 'C', 'B'))

move A->C
move A->B
move C->B
move A->C
move B->A
move B->C
move A->C
7

步数满足 T(n) = 2T(n-1) + 1，所以 T(n) = 2^n - 1。三个盘子 7 步，64 个盘子要 2^64 - 1 步。这里的指数增长是问题本身决定的；但下一节会看到，很多树递归的指数增长是我们自己造成的浪费。

停一下，检查理解单选

count_partitions(n, m) 里为什么 n == 0 返回 1 而不是 0？

因为 0 本身也算一种划分方式，所以要多加 1走到 n == 0 说明之前选的数恰好加起来等于原来的 n，这条路径对应一种合法写法为了避免递归无限进行，返回什么都可以因为 m 此时也一定是 0

检查答案

记忆化：别把同一件事算两遍

Fibonacci 数的定义是 fib(n) = fib(n-1) + fib(n-2)，照抄成代码就是一个树递归。数一下它调用了多少次：

calls = 0
def fib(n):
    global calls
    calls += 1
    if n < 2:
        return n
    return fib(n-1) + fib(n-2)
print(fib(25), calls)

75025 242785

算第 25 项调用了 24 万次。画出调用树就明白了：fib(25) 调用 fib(24) 和 fib(23)，fib(24) 又调用 fib(23) 和 fib(22)……fib(23) 被算了 2 次，fib(22) 被算了 3 次，越往下重复越多，总调用次数和 fib(n) 本身一样按大约 1.618^n 指数增长。

问题本身并不难：只有 26 个不同的子问题 fib(0) 到 fib(25)。浪费来自重复计算同一个子问题。修正的办法是把算过的结果存起来，下次直接查表。这叫记忆化（memoization），用高阶函数写出来正好把这一篇的两条线接上：

def memo(f):
    cache = {}
    def g(n):
        if n not in cache:
            cache[n] = f(n)
        return cache[n]
    return g
calls = 0
fib = memo(fib)
print(fib(25), calls)

75025 26

从 24 万次降到 26 次。三件事同时在起作用：

• memo 是高阶函数，接收一个函数、返回一个增强版。
• g 是闭包，cache 活在 memo 的调用帧里，每次调用 g 都能看到同一个字典。
• fib = memo(fib) 重新绑定了全局名字 fib。原函数体里递归调用写的是 fib(n-1)，这个名字在调用时去全局帧查，现在查到的是带缓存的 g，所以递归内部的每一次调用也都走缓存。如果写成 fast = memo(fib) 而不改全局名字，只有最外层一次被缓存，内部递归还是原来的指数级。

记忆化只对纯函数安全：缓存的前提是同样的参数永远得到同样的结果。这呼应了上一篇区分纯与非纯函数的理由。标准库的 functools.lru_cache 就是一个工程化的 memo。

把”缓存子问题”系统化，从小到大依次填表，就是动态规划，它属于 算法设计。

停一下，检查理解单选

执行 fast = memo(fib)（不改全局名字 fib）后调用 fast(25)，调用次数会怎样？

和 fib = memo(fib) 一样，只有 26 次几乎没有改善，因为 fib 函数体内部的递归调用仍然查到全局里未缓存的原函数报错，因为 fib 已经被 memo 包装过了，不能再直接调用变成 0 次，因为结果是直接从缓存读出的

检查答案

记住这三件事

1. 函数是值：高阶函数把”做什么”也变成参数，lambda、currying、装饰器都是在这之上的写法，装饰器只是 f = deco(f) 的语法糖。
2. 闭包 = 函数 + 定义时的帧；它记住的是帧里的名字，所以调用时看到的是名字当时的值。
3. 递归靠信任跳跃写对：基本情况、用更小问题拼出答案、向基本情况靠近；树递归里重复的子问题用记忆化消掉。

延伸阅读

• Composing Programs 1.6 Higher-Order Functions（CC BY-SA）
• Composing Programs 1.7 Recursive Functions（CC BY-SA）
• CS61A 课程主页（Hog 项目大量使用高阶函数）
• SICP 1.2 Procedures and the Processes They Generate
• Python 文档：functools（partial、lru_cache、wraps）