HW 1：函数、控制、高阶函数ok 5 项通过

0. 这份作业在练什么

HW 1 一共六道题，前四道是必做（Q1–Q4），后两道是可选（Q5–Q6）。本仓库里 hw/hw01/hw01.py 把六道题全部写完了，跑 python3 ok --local 的结果是 5 test cases passed! No cases failed.——注意这个 5 是 ok 评分器统计的 「test case」条数，不是题目数；六道题的 doctest 全部通过，没有任何一项失败。这一点如实写在这里， 免得你对着数字发愣。

这份作业没有 What-Would-Python-Display 概念题（hw/hw01/tests/ 目录下只有一个空的 __init__.py，所有测试都是从 hw01.py 的 docstring 里直接抽出来的 doctest）。 所以本页就是六道编程题，每题按「题目要什么 → 怎么想到的 → 代码逐行讲 → 手动验证」四步展开。

它对应哪几讲

做之前你必须已经掌握的三件事

文件里已经给好的辅助函数

hw01.py 顶部预置了四个单参数函数，Q3、Q4、Q6 的 doctest 全靠它们当「测试用的 term」：

from operator import add, mul

def square(x):
    return x * x

def identity(x):
    return x

def triple(x):
    return 3 * x

def increment(x):
    return x + 1

这四个函数本身毫无技术含量，但它们的存在方式很关键：square 不是「一段要复制粘贴的代码」， 而是一个可以被当成实参传来传去的值。整份作业的高阶函数部分，就是围绕这个事实展开的。 另外第一行的 from operator import add, mul 把内置算术运算的函数版本拿了进来： add(2, 3) 与 2 + 3 求值结果完全一样，区别只在于前者是个可以传递的对象，后者是一段语法。

1. Q1：A Plus Abs B

题目要什么

写一个函数 a_plus_abs_b(a, b)，返回 a + abs(b)，但是不许调用 abs。而且题面已经把函数的骨架给好了，你只能填两个空， 其余一个字都不能改——尤其是最后那行 return f(a, b)，ok 里有一个专门的语法检查 a_plus_abs_b_syntax_check，它会用 inspect 把你的源码抠出来正则匹配， 确认这一行还是原样：

>>> import inspect, re
>>> re.findall(r'^\s*(return .*)', inspect.getsource(a_plus_abs_b), re.M)
['return f(a, b)']

这条检查的意思是：函数体里有且只有一条 return 语句，而且必须是 return f(a, b)。所以任何形如 return a - b、 return a + (-b) 的写法，哪怕答案对，也会被这条测试判负。

四条 doctest 覆盖了 b 的正负与 a 的正负的四种组合：

>>> a_plus_abs_b(2, 3)
5
>>> a_plus_abs_b(2, -3)
5
>>> a_plus_abs_b(-1, 4)
3
>>> a_plus_abs_b(-1, -4)
3

边界情况：b == 0。题面没测，但你要想清楚—— abs(0) 是 0，此时走 add 还是走 sub 都得到 a，两条分支殊途同归。所以判断条件写 b < 0 还是 b <= 0 都不影响正确性；但 b > 0 与 b < 0 谁在 if 谁在 else 是有讲究的，下面会说。

怎么想到的

第一反应几乎所有人都一样：abs(b) 不就是「b 是负数就取相反数」吗？于是想写

if b < 0:
    return a - b
else:
    return a + b

这个想法本身完全正确，数学上也无懈可击：当 b < 0 时 -b = abs(b)， 所以 a - b == a + abs(b)。但它过不了语法检查——因为它写了两条 return，而且都不是 return f(a, b)。

于是被迫回头看题面给的骨架。骨架最后一行是 return f(a, b)，这句话在逼你回答一个问题： f 是什么？它出现在函数调用的算子（operator）位置上，说明它必须求值成一个 能被调用的、接受两个参数的东西。而题面第一段刚好告诉你： operator 模块里有 add 和 sub 这样的双参数函数， add(2, 3) 和 2 + 3 是一回事。

这个转换是 CS 61A 反复要教的思维方式：控制流的差异可以被降级成数据的差异。 原本 if 分支里放的是两段行为，现在分支里放的是两个值，行为只有一份。 后面 Q6 的 accumulate 把 fuse 做成参数，用的是完全同一招—— 只不过 Q1 是你自己在函数体内选，Q6 是让调用者从外面传进来。

还有一个小弯路值得记：有人会写 f = sub(a, b)，然后 return f(a, b) 报

TypeError: 'int' object is not callable

原因是 sub(a, b) 已经把函数调用掉了，f 拿到的是一个整数， 而整数不能再加括号调用。要绑定函数本身，就不能写括号：f = sub。 这是「名字 vs 调用」的第一次正面交锋，务必分清。

代码逐行讲

from operator import add, sub

def a_plus_abs_b(a, b):
    """Return a+abs(b), but without calling abs.

    >>> a_plus_abs_b(2, 3)
    5
    >>> a_plus_abs_b(2, -3)
    5
    >>> a_plus_abs_b(-1, 4)
    3
    >>> a_plus_abs_b(-1, -4)
    3
    """
    if b < 0:
        f = sub    # b is negative, so a - b == a + abs(b)
    else:
        f = add    # b is non-negative, so a + b == a + abs(b)
    return f(a, b)

• from operator import add, sub：这行是题面预置的。它在当前全局帧里创建了两个名字 add 和 sub，分别绑定到内置的加法函数与减法函数对象。 注意 hw01.py 开头还有一行 from operator import add, mul（给 Q6 用的）， 两行不冲突，只是往同一个全局帧里多绑几个名字。
• if b < 0:：条件只关心 b 的符号，与 a 无关—— 因为 abs 只作用在 b 上。写成 b < 0 而不是 b > 0，是为了让「非负」这个包含 0 的情况落到 else 里， 读起来是「负数才需要特殊处理」，符合直觉。
• f = sub：赋值语句，不是调用。执行后，当前局部帧里多了一个绑定 f → 减法函数。sub 后面没有括号，这是全题的题眼。
• f = add：同理，f 指向加法函数。两条分支之后，无论走哪边， f 都是一个「能吃两个数、吐一个数」的函数。这就是所谓的接口一致： 不同的值，相同的用法。
• return f(a, b)：题面给定，不可改。求值顺序是——先求算子 f（得到某个函数对象）， 再求两个算子数 a、b，然后把这两个值送进那个函数，得到结果并返回。 如果你在这一行之前忘了给 f 赋值，就会看到 NameError: name 'f' is not defined。

验证：手动追踪 a_plus_abs_b(-1, -4)

挑最容易出符号错误的一组：a = -1，b = -4，期望答案 -1 + abs(-4) = -1 + 4 = 3。

Global frame
    add  → 内置函数 add
    sub  → 内置函数 sub
    a_plus_abs_b → func a_plus_abs_b(a, b)

f1: a_plus_abs_b   [parent = Global]
    a  = -1
    b  = -4
    ---- 执行 if b < 0 → -4 < 0 → True，进入 then 分支
    f  → 内置函数 sub          （新增绑定）
    ---- 执行 return f(a, b)
         求算子 f      → 减法函数
         求算子数 a    → -1
         求算子数 b    → -4
         调用 sub(-1, -4) → -1 - (-4) → 3
    返回值 = 3

2. Q2：Hailstone

题目要什么

冰雹序列（hailstone sequence，又叫 Collatz 序列）的规则只有三条：

函数 hailstone(n) 要做两件事：把序列里经过的每一个数 逐行打印出来，同时返回序列的长度（也就是打印了多少个数）。

>>> a = hailstone(10)
10
5
16
8
4
2
1
>>> a
7
>>> b = hailstone(1)
1
>>> b
1

这段 doctest 的写法本身就在教你东西。为什么写 a = hailstone(10) 而不是直接 hailstone(10)？因为如果直接写，交互式解释器会既显示打印的 7 行，又显示返回值 7，一共 8 行输出，读起来分不清哪行是 print 的、哪行是返回值的。 先把返回值接到变量 a 里，屏幕上就只剩下 print 的 7 行； 下一句单独求值 a，才把返回值 7 显示出来。 doctest 在用排版帮你区分「副作用」和「返回值」。

边界情况有两个，都要盯紧：

• hailstone(1)：序列只有一个数 1，要打印一行 1，返回 1。 题面明确说了 “Note that if n == 1 initially, then the sequence is one step long.” 这意味着长度计的是「数的个数」，不是「变换的次数」。
• 打印的必须是整数 4，不能是浮点数 4.0。 Python 3 里 8 / 2 求值成 4.0（float），只有 8 // 2 才是 4（int）。doctest 是逐字符比对输出的，打出 4.0 就算错。

怎么想到的

先把「要维护什么」列清楚。序列在往前走，每一步都有两样东西在变：

循环条件呢？「一直做到 n 变成 1」，直译就是 while n != 1:。

写到这里第一版很自然长这样：

length = 1
while n != 1:
    print(n)
    if n % 2 == 0:
        n = n // 2
    else:
        n = 3 * n + 1
    length = length + 1
return length

然后它错了。拿 hailstone(10) 试：打印出 10、5、16、8、4、2， 到 n 变成 1 时循环条件为假，直接退出——最后那个 1 没被打印。 输出只有 6 行，doctest 要 7 行。

怎么补？有两条路，值得都想一遍：

路线 A：把 print 挪到循环外面补一次。 循环退出时 n 一定是 1（这是 while n != 1 的直接推论）， 所以在 return 之前加一行 print(n) 就补上了。 而且这行对 hailstone(1) 也刚好正确——那次循环一次都没进， length 保持初值 1，然后打印一行 1，返回 1，正是边界要求。 一处修改同时解决了主流程和边界，这是好设计的信号。

路线 B：改用 while True + 中途 break。 先 print(n)，再判断 if n == 1: break，然后更新。 逻辑上也对，但多了一个 break，而且 length 的加一位置更容易搞混。 既然路线 A 只多一行且不引入新控制结构，就用 A。

再确认一下 length 的加一位置。它必须放在 n 更新之后 （或者说，与「产生了一个新数」这件事绑定），因为初值 1 已经把起点算进去了， 之后每产生一个新数才 +1。如果 length 初值写 0，那就得在循环外补 +1， 反而更绕——初值 1 是对边界情况 n == 1 的直接呼应。

最后是除法。写 n = n / 2 的话，10 / 2 是 5.0， 往后整条序列全变成浮点数，打印出 16.0、8.0……而且 n != 1 在 n 是 1.0 时其实是 False （1.0 == 1 为真），循环还是会正常结束，只是输出全带小数点，doctest 全挂。 所以必须用整除 //——题面的 Hint 说的就是这件事。

代码逐行讲

def hailstone(n):
    """Print the hailstone sequence starting at n and return its
    length.

    >>> a = hailstone(10)
    10
    5
    16
    8
    4
    2
    1
    >>> a
    7
    >>> b = hailstone(1)
    1
    >>> b
    1
    """
    length = 1              # the starting value n counts as the first step
    while n != 1:
        print(n)
        if n % 2 == 0:
            n = n // 2      # floor division keeps n an int (4, not 4.0)
        else:
            n = 3 * n + 1
        length = length + 1
    print(n)                # n is now 1, the last value of the sequence
    return length

• length = 1：起点 n 自己就是序列的第一个元素，所以从 1 起算。 这一行同时也是 hailstone(1) 能返回 1 的全部原因。
• while n != 1:：只要还没到 1 就继续。用 != 而不是 > 1， 两者对正整数等价，但 != 1 更贴近题面「continue until n is 1」的字面意思。
• print(n)（循环内）：打印当前这个数，然后才把它变成下一个。 顺序很重要：先打印再更新，才能保证打印的是「进入本轮时的 n」。
• if n % 2 == 0:：n % 2 是 n 除以 2 的余数， 偶数余 0。这里必须写 == 0 而不是 n % 2（后者虽然在 Python 里 0 也会被当作假，能跑通，但 61A 的风格是让条件显式表达布尔含义）。
• n = n // 2：整除。// 对两个 int 求值仍得 int。 这是整道题唯一的「语言陷阱」。
• n = 3 * n + 1：奇数规则。注意 3 * n + 1 的运算优先级—— 乘法先于加法，不需要括号。
• length = length + 1：刚刚产生了一个新的 n，序列多了一项。 放在 if/else 之后，两条分支共用一份，不用写两遍。
• print(n)（循环外）：循环退出说明 n == 1，把最后这个 1 补打印出来。 如果 n 一开始就是 1，循环体一次都没执行，这行就是唯一的输出。
• return length：把长度交回调用者。注意它在循环外面—— 写进循环里会导致第一轮就返回，函数直接结束。

验证：手动追踪 hailstone(10)

再追一遍边界 hailstone(1)：length = 1；检查 1 != 1 得 False，循环体一次都不执行；执行循环外的 print(n) 打印 1；return 1。输出一行 1，返回 1——正确。

3. Q3：Product

题目要什么

写 product(n, term)，返回某个序列前 n 项的乘积： term(1) * term(2) * ... * term(n)。

关键在于第二个参数 term 不是一个数，是一个函数。 题面写得很清楚：“term: a function that takes an index as input and produces a term”， 也就是 term(i) 给出序列的第 i 项。序列长什么样，完全由调用者传进来的 term 决定；product 自己不知道、也不需要知道。

>>> product(3, identity)  # 1 * 2 * 3
6
>>> product(5, identity)  # 1 * 2 * 3 * 4 * 5
120
>>> product(3, square)    # 1^2 * 2^2 * 3^2
36
>>> product(5, square)    # 1^2 * 2^2 * 3^2 * 4^2 * 5^2
14400
>>> product(3, increment) # (1+1) * (2+1) * (3+1)
24
>>> product(3, triple)    # 1*3 * 2*3 * 3*3
162

六条 doctest 里 n 没变多少，变的全是 term： identity 让它算阶乘，square 让它算平方之积， increment 让它算 2*3*4，triple 让它算 3*6*9。 同一段循环代码，靠换一个参数就生成了四种完全不同的数学函数—— 这就是高阶函数（higher-order function）的全部意义。

边界情况：docstring 里注明 “n: a positive integer”，所以理论上不用管 n == 0。但下面的写法用的是 while k <= n， n 为 0 时循环一次都不进、直接返回 1，这恰好是数学上「空乘积等于 1」的正确答案， 白捡一个健壮性。这一点在 Q6 的 accumulate 里会变成必须—— 那里的 doctest 明确测了 n == 0。

怎么想到的

如果 term 让你发懵，先做个降维练习：假装题目只要算阶乘。 那你会写

total, k = 1, 1
while k <= n:
    total = total * k
    k = k + 1
return total

这个骨架你在 Q2 里已经练过——两个状态变量，一个装累积结果，一个装计数器。 现在回头看：阶乘版里被乘进去的是 k 本身；平方之积版要乘 k * k； 三倍版要乘 3 * k。三个版本只有一个位置不同，就是 「由下标 k 算出这一项的值」这一步。

于是把 total * k 改成 total * term(k)，题就做完了。 真正需要在脑子里过关的是这一句：term 是个名字，它当前绑定到某个函数对象； term(k) 才是把那个函数调用起来、得到一个数。 和 Q1 里的 f = sub / f(a, b) 是同一个道理，只是这回函数是从外面传进来的。

几个想歪了的方向，也说一下：

• 想写 total = total * term：把函数对象直接乘进去，报 TypeError: unsupported operand type(s) for *: 'int' and 'function'。 少写了括号，函数就没被调用。
• 想在 product 里 if term == square: ... elif term == identity: ...： 能跑，但完全违背了这道题的目的——你又把 term 当成了一个「标签」而不是一段可执行的计算， 而且遇到没见过的 term 就废了。
• 累积变量从 0 开始：total = 0，那么第一次 0 * term(1) 就是 0， 之后永远是 0。乘法的单位元（identity element）是 1，不是 0。 这个「起始值必须是运算的单位元」的观察，正是 Q6 要把 start 做成参数的原因。

下标从哪开始？题目说 term(1) * ... * term(n)，所以 k 从 1 开始，循环条件是 k <= n（含 n）。 写成 k < n 会少乘最后一项：product(3, identity) 得 2 而不是 6。

代码逐行讲

def product(n, term):
    """Return the product of the first n terms in a sequence.

    n: a positive integer
    term: a function that takes an index as input and produces a term

    >>> product(3, identity)  # 1 * 2 * 3
    6
    >>> product(5, identity)  # 1 * 2 * 3 * 4 * 5
    120
    >>> product(3, square)    # 1^2 * 2^2 * 3^2
    36
    >>> product(5, square)    # 1^2 * 2^2 * 3^2 * 4^2 * 5^2
    14400
    >>> product(3, increment) # (1+1) * (2+1) * (3+1)
    24
    >>> product(3, triple)    # 1*3 * 2*3 * 3*3
    162
    """
    total, k = 1, 1         # 1 is the identity for multiplication
    while k <= n:
        total = total * term(k)
        k = k + 1
    return total

• total, k = 1, 1：一条语句同时建立两个绑定。 右边的 1, 1 先被求值成一个二元组，再按位置拆给左边两个名字。 total 初值取 1 是因为它是乘法单位元——任何数乘 1 不变， 所以「还没乘任何东西」的状态就该是 1。k 初值取 1 是因为序列从第 1 项算起。
• while k <= n:：含 n。 循环体一共执行 n 次，k 依次取 1, 2, …, n。
• total = total * term(k)：求值顺序是——先算右边整个表达式： 取出 total 当前的值，调用 term(k) 得到第 k 项， 两者相乘；然后把结果重新绑定给 total。 term(k) 的括号是全题的核心，没有它就不是调用。
• k = k + 1：推进计数器。忘了这行会得到无限循环—— k 永远是 1，条件永远真，程序挂死（要 Ctrl-C 才停）。
• return total：在循环外。放循环里的话第一轮就返回， product(3, identity) 会得到 1 而不是 6。

顺带一提：这里也可以写成 total, k = total * term(k), k + 1 合成一行。 效果相同（右边先整体求值，所以用的都是旧的 k），但分成两行更好读，也更不容易搞错顺序。

验证：手动追踪 product(3, square)

square 是文件顶部定义的 def square(x): return x * x。 期望结果 1² * 2² * 3² = 1 * 4 * 9 = 36。

Global frame
    square  → func square(x)
    product → func product(n, term)

f1: product   [parent = Global]
    n     = 3
    term  → func square(x)        ← 注意：绑定的是函数对象本身
    total = 1,  k = 1

  第 1 轮： k <= n → 1 <= 3 → True
      调用 square(1) ──→ f2: square [parent=Global]  x = 1  返回 1
      total = 1 * 1 = 1
      k = 2
  第 2 轮： 2 <= 3 → True
      调用 square(2) ──→ f3: square  x = 2  返回 4
      total = 1 * 4 = 4
      k = 3
  第 3 轮： 3 <= 3 → True
      调用 square(3) ──→ f4: square  x = 3  返回 9
      total = 4 * 9 = 36
      k = 4
  检查： 4 <= 3 → False，退出循环
    return total → 36

为什么这道题值得反复回味

4. Q4：Make Repeater

题目要什么

make_repeater(f, n) 接受一个单参数函数 f 和一个正整数 n， 返回一个新的单参数函数。这个新函数拿到 x 之后， 把 f 连续套用 n 次：f(f(...f(x)...))。

>>> add_three = make_repeater(increment, 3)
>>> add_three(5)
8
>>> make_repeater(triple, 5)(1) # 3 * (3 * (3 * (3 * (3 * 1))))
243
>>> make_repeater(square, 2)(5) # square(square(5))
625
>>> make_repeater(square, 3)(5) # square(square(square(5)))
390625

先把 doctest 的写法读懂，因为它包含了这道题最重要的信息：

• add_three = make_repeater(increment, 3)：调用 make_repeater 不产生任何数字，它产生一个函数，然后被绑定到名字 add_three。 此时还没有任何 increment 被执行过。
• add_three(5)：现在才真正干活，把 increment 套 3 次到 5 上， 得到 5 → 6 → 7 → 8。
• make_repeater(triple, 5)(1)：两对括号。 第一对调用 make_repeater 得到函数，第二对立刻调用那个函数。 这个写法在 61A 后面会出现无数次，现在就要看顺眼。

边界情况：题面说 n 是 positive integer，所以不必处理 n == 0。 但下面的写法在 n == 0 时会原样返回 x（f 套 0 次就是不动）， 这在数学上也是对的——它相当于恒等函数。顺带说，make_repeater(square, 3)(5) 的结果 390625 值得自己算一下确认理解：5² = 25，25² = 625， 625² = 390625。不是 5^(2*3) = 15625—— 反复平方是指数翻倍，套 3 次得到的是 5^(2³) = 5^8。

怎么想到的

第一个坎：函数怎么可能被 return？ 如果你接受了 Q1 的 f = sub（函数可以绑给变量）和 Q3 的 term （函数可以当参数），那 return 一个函数就没有任何新鲜之处—— 函数就是一种普通的值，能赋值、能传参，当然也能返回。 Python 里用 def 在函数体内部再定义一个函数，然后 return 那个名字即可。

第二个坎：返回的那个函数，怎么知道 f 和 n 是谁？ 这才是本题的真正内容。答案是：内层函数 repeat 是在 make_repeater 的帧里被定义的，所以它的 parent 指向那一帧； 之后调用 repeat(x) 时，x 在自己的局部帧里找得到， 而 f 和 n 在局部帧里找不到，就顺着 parent 链找到 make_repeater 的帧，在那里找到。这种「函数记住了它出生环境」的现象叫 闭包（closure）。

第三个坎：套 n 次怎么写？ 这里可以走两条路，都值得看清楚。

路线 A（本仓库采用）：在内层用 while 循环反复覆盖 x。 维护两个状态：当前值 x，已经套了几次 k。 每轮 x = f(x)、k = k + 1，套满 n 次退出。 这跟 Q2、Q3 的循环骨架是同一套东西，你已经熟了。

路线 B：递归地构造函数。 make_repeater(f, n) 可以写成「先套一次 f，再交给 make_repeater(f, n-1)」，base case 是 n == 0 时返回 identity。写法漂亮，但它每次调用都新建 n 层嵌套的函数对象， 理解成本更高。作业只要求正确，路线 A 更直白，也更贴合本周讲过的内容。

路线 A 有一个容易踩的坑：能不能在内层直接写 n = n - 1 来倒着数？ 不能。repeat 里给 n 赋值，Python 会把 n 当成 repeat 的局部变量，而它在被赋值前又被 while n > 0 读了一次，于是报

UnboundLocalError: local variable 'n' referenced before assignment

（就算能改，也会有另一个问题：n 被改小之后，同一个 repeater 第二次调用就废了。） 所以正确做法是另开一个计数器 k，只读 n、不写 n。 这一点是整道题最实用的教训。

代码逐行讲

def make_repeater(f, n):
    """Returns the function that computes the nth application of f.

    >>> add_three = make_repeater(increment, 3)
    >>> add_three(5)
    8
    >>> make_repeater(triple, 5)(1) # 3 * (3 * (3 * (3 * (3 * 1))))
    243
    >>> make_repeater(square, 2)(5) # square(square(5))
    625
    >>> make_repeater(square, 3)(5) # square(square(square(5)))
    390625
    """
    def repeat(x):
        k = 0
        while k < n:        # apply f exactly n times
            x = f(x)
            k = k + 1
        return x
    return repeat

• def repeat(x):：在 make_repeater 的帧里创建一个函数对象， 并把名字 repeat 绑给它。这一行不执行函数体， 只是「造一个函数」。函数对象里记着它的 parent 是当前这一帧。
• k = 0：计数器从 0 开始，配合 while k < n， 循环体正好执行 n 次（k 取 0, 1, …, n-1）。 写 k = 1 配 k <= n 也一样，挑一套记熟即可。
• while k < n:：n 在 repeat 的局部帧里没有， Python 顺着 parent 找到 make_repeater 的帧，读到当初传进来的那个值。 这就是闭包在起作用。注意这里只读不写。
• x = f(x)：这一行做了两件事——调用 f（同样是顺 parent 链找到的）， 把结果重新绑给 repeat 的局部变量 x。 「用旧值算新值再覆盖」是循环里最常见的模式。x 是局部的， 所以外面的世界不受影响，同一个 repeater 可以重复调用。
• k = k + 1：推进计数器。
• return x（内层）：套完 n 次后的最终值。
• return repeat（外层）：没有括号。 返回的是函数对象本身，不是调用它。写成 return repeat(x) 会直接报 NameError: name 'x' is not defined——make_repeater 的帧里根本没有 x。

验证：手动追踪 make_repeater(increment, 3) 再调用 (5)

第一阶段：造函数。执行 add_three = make_repeater(increment, 3)。

Global frame
    increment    → func increment(x)
    make_repeater→ func make_repeater(f, n)
    add_three    → func repeat(x)  [parent = f1]     ← 调用结束后才建立

f1: make_repeater   [parent = Global]
    f      → func increment(x)
    n      = 3
    repeat → func repeat(x)  [parent = f1]   ← def 语句造出来的
    返回值 = func repeat(x)  [parent = f1]

★ f1 这一帧在 make_repeater 返回后并不消失，
  因为 repeat 还指着它当 parent。f 和 n 就活在这里。

第二阶段：用函数。执行 add_three(5)。

f2: repeat   [parent = f1]      ← parent 是 f1，不是 Global！
    x = 5
    k = 0

  查 while k < n：k=0 在 f2 找到；n 在 f2 没有 → 去 f1 找到 3
  第 1 轮： 0 < 3 True
      f 在 f2 没有 → 去 f1 找到 increment
      调用 increment(5) ─→ f3: increment [parent=Global] x=5 返回 6
      x = 6   （改的是 f2 里的 x）
      k = 1
  第 2 轮： 1 < 3 True
      increment(6) → 7
      x = 7 ,  k = 2
  第 3 轮： 2 < 3 True
      increment(7) → 8
      x = 8 ,  k = 3
  检查： 3 < 3 False，退出
    return x → 8

输出 8，与 doctest 一致。

三层抽象的对比

5. Q5：Largest Factor（可选题）

题目要什么

给一个大于 1 的整数 n，返回比 n 小的、能整除 n 的最大整数。

>>> largest_factor(15) # factors are 1, 3, 5
5
>>> largest_factor(80) # factors are 1, 2, 4, 5, 8, 10, 16, 20, 40
40
>>> largest_factor(13) # factors are 1, 13
1

三条 doctest 挑得很有心机：

• 15：合数，答案 5（15 = 3 × 5）。
• 80：因数很多，答案 40，也就是 80 / 2——这提示了一个规律， 偶数的最大真因数就是它的一半。
• 13：质数，比它小的因数只有 1，答案就是 1。 这是必须单独想清楚的边界：质数的循环会一路数到 1 才停。

题面明确 “takes an integer n that is greater than 1”，所以不用考虑 n = 1（那样 factor 从 0 起步，第一步就 n % 0 触发 ZeroDivisionError）和负数。题面的 Hint 也把判断整除的方法给了： a % b == 0 表示「a 除以 b 余数为 0」，即 b 整除 a。

怎么想到的

「最大的、满足某条件的数」——这类问题有个万能套路：从最大的候选开始往下试， 第一个满足条件的就是答案。因为是从大到小扫的，第一个命中的必然最大，不用比较、不用记录。

那最大的候选是谁？题目要求「比 n 小」，所以候选从 n - 1 起， 往下 n - 2、n - 3……最小到 1。

条件是什么？n % factor == 0。

接下来是写法上的一个小选择。最直白的是「循环里判断，命中就 return」：

factor = n - 1
while factor > 0:
    if n % factor == 0:
        return factor
    factor = factor - 1

这也是官方解答的写法，完全正确。但仔细想想：这个循环真的需要 factor > 0 这个保险吗？不需要。因为 1 整除任何整数，n % 1 恒为 0， 所以扫到 1 的时候一定命中，factor 永远不会掉到 0 以下。 既然循环一定会因为「找到因数」而停止，就可以把「找到因数」直接写成循环条件的否定：

factor = n - 1
while n % factor != 0:
    factor = factor - 1
return factor

这版少了一层 if，也少了一个 return，循环体只剩一行。 读起来是「只要 factor 还不能整除 n，就继续往下找」，非常贴近口语描述。 本仓库用的是这一版。

代码逐行讲

def largest_factor(n):
    """Return the largest factor of n that is smaller than n.

    >>> largest_factor(15) # factors are 1, 3, 5
    5
    >>> largest_factor(80) # factors are 1, 2, 4, 5, 8, 10, 16, 20, 40
    40
    >>> largest_factor(13) # factors are 1, 13
    1
    """
    factor = n - 1          # search downward for the first divisor of n
    while n % factor != 0:
        factor = factor - 1
    return factor

• factor = n - 1：最大的合法候选。写 n 就错了—— n % n == 0 立刻成立，会返回 n 自己，而题目要求「比 n 小」。 这是本题唯一的一个「差一」陷阱。
• while n % factor != 0:：循环条件是「还没找到」。 % 是取模运算符，n % factor 是 n 除以 factor 的余数。余数不为 0 说明除不尽，继续找。
• factor = factor - 1：往下一个候选。循环体只有这一行—— 所有判断都在条件里做完了。
• return factor：循环退出意味着条件为假，即 n % factor == 0， 也就是当前的 factor 整除 n。因为是从大往小扫的，它就是最大的那个。 注意 return 在循环外，返回的是「导致循环停下的那个值」。

验证：手动追踪三条 doctest

6. Q6：Accumulate（可选题）

题目要什么

这题分三小问。第一问实现 accumulate(fuse, start, n, term)， 它是 product 的进一步一般化：把序列的前 n 项 term(1), term(2), ..., term(n) 与初值 start 用双参数函数 fuse 依次「熔合」起来。四个参数各司其职：

>>> accumulate(add, 0, 5, identity)  # 0 + 1 + 2 + 3 + 4 + 5
15
>>> accumulate(add, 11, 5, identity) # 11 + 1 + 2 + 3 + 4 + 5
26
>>> accumulate(add, 11, 0, identity) # 11 (fuse is never used)
11
>>> accumulate(add, 11, 3, square)   # 11 + 1^2 + 2^2 + 3^2
25
>>> accumulate(mul, 2, 3, square)    # 2 * 1^2 * 2^2 * 3^2
72
>>> # 2 + (1^2 + 1) + (2^2 + 1) + (3^2 + 1)
>>> accumulate(lambda x, y: x + y + 1, 2, 3, square)
19

三个必须盯住的点：

• 第三条 accumulate(add, 11, 0, identity) 返回 11， 注释还特意写了 “fuse is never used”。n == 0 时循环一次都不能进，直接返回 start。这是 n 被声明为「非负整数」而不是「正整数」的原因， 也是本题唯一硬性的边界要求。
• 最后一条的 fuse 是个 lambda x, y: x + y + 1， 不满足「fuse(a, b) 就是简单加法」的直觉。它存在的意义是防止你偷懒—— 如果你把 fuse 写死成 + 或者调换参数顺序做了什么手脚， 这条会立刻暴露。
• 题面明确 “Assume that fuse is commutative and associative”， 即 fuse(a,b) == fuse(b,a) 且 fuse(fuse(a,b),c) == fuse(a,fuse(b,c))。 这句话给了你自由：不必按题面示例里那种右结合的嵌套顺序去算， 从左往右一路累积得到的结果是一样的。

第二、三问要求把 summation_using_accumulate 和 product_using_accumulate 各写成一行 return。 doctest 里有一条用 ast 检查函数体结构：

>>> import inspect, ast
>>> [type(x).__name__ for x in ast.parse(inspect.getsource(summation_using_accumulate)).body[0].body]
['Expr', 'Return']

它把函数源码解析成语法树，列出函数体里每条语句的类型，要求正好是 ['Expr', 'Return']——Expr 是那段 docstring（docstring 在语法树里 就是一条表达式语句），Return 是你写的那一行。多写任何一条语句都会失败。

怎么想到的

先把 Q3 的 product 和一个假想的 summation 并排放着看：

五行里有三行完全一样，只有初值和合并运算不同。 按 Q1 学到的那一招——「控制流的差异降级成数据的差异」——把这两处提成参数就完了： 初值提成 start，运算提成 fuse。运算是一段计算，所以它得是个函数， 写成 fuse(total, term(k))。

然后是 n == 0 的边界。好消息是不用任何特殊处理： total 初始化成 start，循环条件 k <= n 在 k = 1、n = 0 时是 1 <= 0 即 False， 循环体一次都不进，直接 return total 即 start。 fuse 确实一次都没被调用，跟注释说的一模一样。 把初值直接放进累加器，边界自动就对了——这是循环写法的一个通用技巧。

再看第二、三问。有了 accumulate，summation 就是 「用 add 熔合、从 0 开始」，product 就是 「用 mul 熔合、从 1 开始」。为什么起始值必须是这两个数？ 因为它们分别是加法和乘法的单位元（identity element）： 0 + x == x，1 * x == x。如果 summation 从 1 起， 结果会整体多 1；如果 product 从 0 起，结果恒为 0。

代码逐行讲

def accumulate(fuse, start, n, term):
    """Return the result of fusing together the first n terms in a sequence
    and start.  The terms to be fused are term(1), term(2), ..., term(n).
    The function fuse is a two-argument commutative & associative function.

    >>> accumulate(add, 0, 5, identity)  # 0 + 1 + 2 + 3 + 4 + 5
    15
    >>> accumulate(add, 11, 5, identity) # 11 + 1 + 2 + 3 + 4 + 5
    26
    >>> accumulate(add, 11, 0, identity) # 11 (fuse is never used)
    11
    >>> accumulate(add, 11, 3, square)   # 11 + 1^2 + 2^2 + 3^2
    25
    >>> accumulate(mul, 2, 3, square)    # 2 * 1^2 * 2^2 * 3^2
    72
    >>> # 2 + (1^2 + 1) + (2^2 + 1) + (3^2 + 1)
    >>> accumulate(lambda x, y: x + y + 1, 2, 3, square)
    19
    """
    total, k = start, 1
    while k <= n:
        total = fuse(total, term(k))
        k = k + 1
    return total

• total, k = start, 1：与 product 唯一的区别就是 total 的初值不再写死 1，而是取自参数 start。 这一处改动同时解决了「起始值可配置」和「n == 0 直接返回 start」两件事。
• while k <= n:：n 为 0 时直接跳过。含 n， 所以 term(n) 会被算进去。
• total = fuse(total, term(k))：参数顺序是「已累积的在前，新项在后」。 题面保证 fuse 可交换，所以写反了对这几条 doctest 也不会翻车 （lambda x, y: x + y + 1 也是对称的）；但按「累积值 + 新项」的顺序写， 语义上更符合 accumulate 这个名字，也和 product 里 total * term(k) 的位置对得上。 注意这一行里有两次函数调用：先 term(k) 算出第 k 项， 再 fuse(...) 把它熔进来。
• k = k + 1、return total：与 product 完全相同。

def summation_using_accumulate(n, term):
    """Returns the sum: term(1) + ... + term(n), using accumulate.
    ...
    """
    return accumulate(add, 0, n, term)


def product_using_accumulate(n, term):
    """Returns the product: term(1) * ... * term(n), using accumulate.
    ...
    """
    return accumulate(mul, 1, n, term)

• accumulate(add, 0, n, term)：add 是加法函数（from operator import add, mul 在文件顶部已经导入），起始值 0 是加法单位元。
• accumulate(mul, 1, n, term)：mul 是乘法函数，起始值 1 是乘法单位元。
• 两者都是单独一行 return，没有临时变量、没有 if， 才能通过那条 ast 结构检查。

验证：手动追踪 accumulate(add, 11, 3, square)

期望 11 + 1² + 2² + 3² = 11 + 1 + 4 + 9 = 25。

再追那条最刁钻的 lambda：accumulate(lambda x, y: x + y + 1, 2, 3, square)。 这里 fuse(x, y) 求值成 x + y + 1，每次熔合都白送一个 +1。

total = start = 2 ,  k = 1

轮 1: term(1) = square(1) = 1
      total = fuse(2, 1)  = 2 + 1 + 1 = 4
轮 2: term(2) = square(2) = 4
      total = fuse(4, 4)  = 4 + 4 + 1 = 9
轮 3: term(3) = square(3) = 9
      total = fuse(9, 9)  = 9 + 9 + 1 = 19
k 变成 4，退出 → return 19

与 doctest 注释 # 2 + (1^2 + 1) + (2^2 + 1) + (3^2 + 1) 对得上： 2 + 2 + 5 + 10 = 19。三次熔合各贡献了一个 +1。

边界 accumulate(add, 11, 0, identity)： total = 11，k = 1；检查 1 <= 0 为 False； 循环体不执行，fuse 一次也没被调用；return 11。正确。

product_using_accumulate(4, square)： 展开成 accumulate(mul, 1, 4, square)， 逐轮 total 为 1 → 1*1=1 → 1*4=4 → 4*9=36 → 36*16=576，返回 576，与 doctest 一致。

7. 整份作业回顾

六道题按题目看是零散的，但它们串起来讲的是同一条线： 函数从「一段被命名的代码」逐步变成「可以像数字一样搬来搬去的值」。

三条最该带走的话

动手练习

下面几题基于本作业的代码，答案折叠在里面。

练习 1. 不改 product 的定义，用它算出 1 + 2 + ... + n 之外的东西： 写一个表达式，算 2 * 4 * 6 * 8 * 10。

练习 2. make_repeater(f, 1)(x) 等于什么？make_repeater(f, 0)(x) 呢？

练习 3. 下面这段代码输出什么？为什么？

def f(x):
    print('called with', x)
    return x + 1

r = make_repeater(f, 3)
print('---')
r(10)

练习 4. 用 accumulate 写出 hailstone 吗？为什么不行？