Lab 3：序列与递归ok 6 项通过

0. 这份作业在练什么

Lab 3 是这门课的一个分水岭。前两次 lab 里，程序处理的东西都是一个数、一个布尔值、一个函数—— 它们都是「原子」的，没有内部结构。从这次开始，程序要处理一堆东西：列表（list）。 而一旦数据本身有了结构，处理它的最自然的手法就不再是 while 循环，而是递归（recursion）： 列表的一部分还是列表，嵌套列表里的元素还是列表，于是「处理一个列表」这件事天然可以拆成 「处理第一个元素」加上「处理剩下的那个更短的列表」。

所以这份作业实际上是两条线拧在一起：

做之前应该已经掌握的东西

• 函数调用的求值过程：先求算子（operator），再求算子数（operand），然后开一个新帧执行函数体。 这在 Q6 make_onion 里会被反复用到——那题的难点根本不是列表，而是「哪个函数在哪个帧里查名字」。
• 递归的三件套：base case（递归基）、递归调用把问题变小、用递归调用的返回值拼出答案。 Lecture 5 讲过的 sum_digits、fact 都是这个模式。
• return 与 print 的区别。这次所有函数都要 return 一个新列表， 一旦写成 print，doctest 会告诉你函数返回了 None。

1. Q1 WWPD：Lists & Ranges

WWPD 是 What Would Python Display 的缩写：给你一串交互式解释器里的输入，让你预测屏幕上会显示什么。 这类题不计分，但它检验的东西比编程题更基础——你脑子里那台「Python 模拟器」准不准。 运行 python3 ok -q lists-wwpd -u 可以逐题作答。

整段题目共用同一行开头的赋值：

>>> s = [7//3, 5, [4, 0, 1], 2]

题目要什么

先把 s 到底是什么算清楚，后面十几问都靠它。[7//3, 5, [4, 0, 1], 2] 是一个 列表字面量（list literal）：方括号里每个表达式各自求值，然后把这些值按顺序装进一个新列表。 注意方括号不是「原样保留」，里面的表达式该算还是要算：

• 7//3 是整除（floor division），得 2，不是 2.33，也不是字符串 "7//3"。
• [4, 0, 1] 本身是一个列表表达式，求值成一个列表对象，然后作为一个元素放进 s。

所以 s 的值是 [2, 5, [4, 0, 1], 2]，它有 4 个元素（不是 6 个）， 其中第 2 号元素本身是一个含 3 个数的列表。

逐问推演

三个最容易错的点，各自展开

s        = [2, 5, [4, 0, 1], 2]
4 in s   →  4 == 2         ? False
         →  4 == 5         ? False
         →  4 == [4, 0, 1] ? False   ← 整数与列表比较，永远不等
         →  4 == 2         ? False
结果：False

s[2] * 2
  = [4, 0, 1] * 2
  = [4, 0, 1] + [4, 0, 1]      ← 乘法就是重复的拼接
  = [4, 0, 1, 4, 0, 1]

想要「每个元素乘 2」必须写列表推导式（Q3 会讲）：
  [x * 2 for x in s[2]]  →  [8, 0, 2]

2. Q2 flatten：把嵌套列表压平

题目要什么

写一个函数 flatten(s)，输入一个列表，返回一个新列表，里面按原顺序装着 s 里所有的「非列表元素」——也就是把所有层的方括号都拆掉，只留下最里面那些真正的值。

>>> flatten([1, 2, 3])
[1, 2, 3]
>>> deep = [1, [[2], 3], 4, [5, 6]]
>>> flatten(deep)
[1, 2, 3, 4, 5, 6]
>>> deep                                # input list is unchanged
[1, [[2], 3], 4, [5, 6]]
>>> very_deep = [['m', ['i', ['n', ['m', 'e', ['w', 't', ['a'], 't', 'i', 'o'], 'n']], 's']]]
>>> flatten(very_deep)
['m', 'i', 'n', 'm', 'e', 'w', 't', 'a', 't', 'i', 'o', 'n', 's']

把这四个 doctest 翻译成人话，其实是四条独立的要求：

题面还额外给了一条边界提示：怎么判断某个东西是不是列表。答案是内建的 type 函数：

>>> type(3) == list
False
>>> type([1, 2, 3]) == list
True

还有一个 doctest 没写但必须想到的边界：空列表。flatten([]) 应该返回 []。 very_deep 那个例子里其实也隐含着「某一层只有一个元素」的情况，处理逻辑必须对任何长度都成立。

怎么想到的

第一反应往往是写循环：遍历 s，遇到普通元素就收下，遇到列表就……就怎么办？ 这里立刻卡住了：遇到列表 [[2], 3]，你想把它「拆开加进去」，可它里面还有列表 [2]。 于是你想再写一层循环。可 very_deep 有五层，你要写五层循环吗？六层的输入怎么办？

把念头写清楚：要压平 s，就把 s 里的每个元素挨个看一遍。

第 2 步就是所谓的递归飞跃（leap of faith）：你必须假设 flatten 对更小的输入已经写对了， 直接拿来用。这时候脑子里不要去展开「那它进去之后又怎么办」——那会一层层想爆炸。 你只需要保证两件事：(a) 递归调用拿到的输入确实更小；(b) 最小的情况能自己停下来。

(a) 成立吗？flatten(element) 里的 element 是 s 的一个元素，嵌套深度比 s 少一层， 一层层剥下去必然会剥到「不含列表的列表」。 (b) 呢？当传进来的列表不含任何子列表时（包括空列表），循环里一次也不会走到递归分支， 函数直接返回收集好的结果——base case 是自动达成的，不需要单独写 if s == []。这一点值得多想一秒钟。

一条走过的弯路

初学者常写出这样的版本：

def flatten(s):        # 错的
    result = []
    for element in s:
        if type(element) == list:
            result = result + element      # ← 问题在这一行
        else:
            result = result + [element]
    return result

它对 [1, [2, 3], 4] 是对的，但对 deep = [1, [[2], 3], 4, [5, 6]] 会返回 [1, [2], 3, 4, 5, 6]——那个 [2] 原封不动地跑进了结果里。 原因是 result + element 只把 element 的顶层元素倒出来， 而 element 的顶层元素里还有列表。把这行改成 result + flatten(element)，问题就解决了： 先把 element 彻底压平，再倒进来。一个字符的差别，却是「只拆一层」和「拆到底」的差别。

代码

def flatten(s: list) -> list:
    result = []
    for element in s:
        if type(element) == list:
            # A nested list: flatten it first, then append all of its items.
            result = result + flatten(element)
        else:
            result = result + [element]
    # `result` is always a brand new list, so `s` is never modified.
    return result

逐行说明为什么是这样而不是别样：

验证

拿 deep = [1, [[2], 3], 4, [5, 6]] 手动跑一遍。为了看清楚，把每次调用标上编号。

调用 A: flatten([1, [[2], 3], 4, [5, 6]])
  result = []
  element = 1          → 不是 list  → result = [] + [1] = [1]
  element = [[2], 3]   → 是 list    → 需要 flatten([[2], 3])，先算它

      调用 B: flatten([[2], 3])
        result = []
        element = [2]  → 是 list    → 需要 flatten([2])

            调用 C: flatten([2])
              result = []
              element = 2 → 不是 list → result = [] + [2] = [2]
              返回 [2]                       ← C 结束

        回到 B: result = [] + [2] = [2]
        element = 3    → 不是 list  → result = [2] + [3] = [2, 3]
        返回 [2, 3]                          ← B 结束

  回到 A: result = [1] + [2, 3] = [1, 2, 3]
  element = 4          → 不是 list  → result = [1, 2, 3] + [4] = [1, 2, 3, 4]
  element = [5, 6]     → 是 list    → 需要 flatten([5, 6])

      调用 D: flatten([5, 6])
        result = []
        element = 5 → result = [5]
        element = 6 → result = [5, 6]
        返回 [5, 6]                          ← D 结束

  回到 A: result = [1, 2, 3, 4] + [5, 6] = [1, 2, 3, 4, 5, 6]
  返回 [1, 2, 3, 4, 5, 6]                    ← 与 doctest 一致

注意调用 C 和调用 D 的共同点：它们的输入 [2]、[5, 6] 不含任何子列表， 所以它们全程走 else 分支，不再产生新的递归调用——递归在这里自然终止。 这就是前面说的「base case 是自动达成的」。

再验一遍「输入未被修改」：整段推演里，s、[[2], 3]、[2]、[5, 6] 这些列表对象一次都没有出现在赋值语句的左边，也没有被调用过任何方法。 每一次 result = result + ... 都是把 result 这个名字重新绑定到一个新造的列表上。 所以 deep 显示出来仍是 [1, [[2], 3], 4, [5, 6]]。

result.append(flatten(element))    # 错

if s == []:
    return []

3. Q3 WWPD：List Comprehensions

列表推导式（list comprehension）是一个表达式，它求值成一个新列表。两种形式：

[<表达式> for <名字> in <序列>]
[<表达式> for <名字> in <序列> if <条件>]

读它的顺序和写的顺序不一样，这是初学者最大的障碍。正确的读法是从中间往两边读：

题面给出的等价 for 语句版本把这个顺序说得最清楚：

>>> [i*i for i in [1, 2, 3, 4] if i % 2 == 0]
[4, 16]

# 等价于：
>>> result = []
>>> for i in [1, 2, 3, 4]:
...     if i % 2 == 0:
...         result = result + [i*i]
>>> result
[4, 16]

逐问推演

第一问：[2 * x for x in range(4)]

range(4) 依次给出  0, 1, 2, 3        ← 不含 4
没有 if，所以每个元素都保留，结果长度 = 4
x = 0 → 2 * 0 = 0
x = 1 → 2 * 1 = 2
x = 2 → 2 * 2 = 4
x = 3 → 2 * 3 = 6
结果：[0, 2, 4, 6]

顺带对比一下 Q1 里的 s[2] * 2。那里是「列表 × 整数 = 重复拼接」， 这里是「对每个元素乘 2」。想要后者，就必须写推导式。 另外注意结果是列表 [0, 2, 4, 6]，不是 range 对象——推导式的产物永远是货真价实的 list。

第二问：[y for y in [6, 1, 6, 1] if y > 2]

y = 6 → 6 > 2 为 True  → 收下 y，即 6
y = 1 → 1 > 2 为 False → 跳过
y = 6 → True           → 收下 6
y = 1 → False          → 跳过
结果：[6, 6]

这里前面的表达式就是 y 本身，也就是只筛选、不变换。 两个 6 都保留，因为推导式是逐位置处理的，它不做去重。 答成 [6] 是常见错误，那是把它当集合看了。

第三问：[[1] + s for s in [[4], [5, 6]]]

这一问最容易慌，因为方括号有三层。拆开看：被遍历的序列是 [[4], [5, 6]]， 它是一个含两个列表的列表，所以 s 每轮绑定到的是一个列表。

序列 [[4], [5, 6]] 有 2 个元素 → 结果长度必为 2

s = [4]     → [1] + [4]     = [1, 4]
s = [5, 6]  → [1] + [5, 6]  = [1, 5, 6]

结果：[[1, 4], [1, 5, 6]]

注意 [1] + s 是列表拼接，不是「把 1 加到 s 上」。 结果的两个元素长度不同（2 和 3），这没关系——列表里的元素可以是任意形状。 最外层的方括号是推导式自己产生的，不要漏掉。

第四问：[z + 1 for z in range(10) if z % 3 == 0]

range(10) 给出 0,1,2,3,4,5,6,7,8,9

z = 0 → 0 % 3 == 0 ? True  → 收下 z + 1 = 1
z = 1 → 1 % 3 == 1        → 跳过
z = 2 → 2 % 3 == 2        → 跳过
z = 3 → True              → 收下 4
z = 4,5 → 跳过
z = 6 → True              → 收下 7
z = 7,8 → 跳过
z = 9 → True              → 收下 10
结果：[1, 4, 7, 10]

这一问同时考了两件事，任何一件搞反都会错：

• 先筛后变换。if 判断的是 z（原元素），不是 z + 1。 如果反过来先加 1 再筛，留下的就会是 z + 1 能被 3 整除的，答案变成 [3, 6, 9]（当 z = 2, 5, 8），完全不同。
• range(10) 不含 10，但结果里有 10——因为 z = 9 时算出 9 + 1 = 10。 这个巧合正好用来检验你有没有把两件事分清楚。

4. Q4 close_list：离自己下标不远的元素

题目要什么

输入一个整数列表 s 和一个非负整数 k，返回 s 中「与自己的下标相差不超过 k」 的那些元素组成的列表。「相差不超过 k」的精确说法是：元素值与它的下标之差的绝对值 ≤ k。

>>> t = [6, 2, 4, 3, 5]
>>> close_list(t, 0)  # Only 3 is equal to its index
[3]
>>> close_list(t, 1)  # 2, 3, and 5 are within 1 of their index
[2, 3, 5]
>>> close_list(t, 2)  # 2, 3, 4, and 5 are all within 2 of their index
[2, 4, 3, 5]

题面给了骨架，明确要求用列表推导式填空：

    assert k >= 0
    return [___ for i in range(len(s)) if ___]

骨架里有两个关键信息，不是随便给的：

• 遍历的是 range(len(s))，即下标 i，不是元素本身。因为条件里要同时用到元素和下标， 写成 for x in s 就拿不到下标了。
• assert k >= 0 已经写好，意思是调用方保证 k 非负，你不用为负数的 k 操心。 顺带说一句 k = 0 是合法输入，此时条件退化成「元素恰好等于下标」。

关于顺序有一条隐含要求：结果必须保持原来的先后顺序。看第三个 doctest，答案是 [2, 4, 3, 5] 而不是排好序的 [2, 3, 4, 5]——因为在 t 里 4 排在 3 前面。 这题不是排序题，只是筛选。用推导式天然满足这一点。

怎么想到的

先把三个 doctest 摊成一张表，把每个位置的「元素 − 下标」算出来，规律立刻就出来了：

三行「保留」和三个 doctest 的答案完全对上：[3]、[2, 3, 5]、[2, 4, 3, 5]。 所以条件就是 abs(s[i] - i) <= k，收下的东西是 s[i]。

一条容易走的弯路：用 for x in s

不看骨架的话，很多人第一反应是 [x for x in s if ...]，写到 if 里才发现—— 我不知道 x 的下标是几。你可能想到用 s.index(x) 去查，但那是错的： index 返回第一次出现的位置，如果列表里有重复元素（比如 [0, 0]）， 第二个 0 会被当成下标 0 处理，判断结果就错了。而且 index 每次都要重新扫一遍列表，效率也差。

正确的做法就是骨架给的：遍历下标，用下标去取元素。 这是「既要元素又要位置」时的标准手法，本课后面处理序列时会一直用。

代码

def close_list(s: list[int], k: int) -> list[int]:
    assert k >= 0
    return [s[i] for i in range(len(s)) if abs(s[i] - i) <= k]

验证

手动跑 close_list([6, 2, 4, 3, 5], 1)。len(s) 是 5，所以 i 依次取 0 到 4。

i = 0: s[0] = 6, abs(6 - 0) = 6, 6 <= 1 ? False → 跳过
i = 1: s[1] = 2, abs(2 - 1) = 1, 1 <= 1 ? True  → 收下 2      结果 [2]
i = 2: s[2] = 4, abs(4 - 2) = 2, 2 <= 1 ? False → 跳过
i = 3: s[3] = 3, abs(3 - 3) = 0, 0 <= 1 ? True  → 收下 3      结果 [2, 3]
i = 4: s[4] = 5, abs(5 - 4) = 1, 1 <= 1 ? True  → 收下 5      结果 [2, 3, 5]

返回 [2, 3, 5]     ← 与 doctest 一致

再快速核一下 k = 2：i = 2 这一位的距离是 2，2 <= 2 成立，于是 4 被收进来， 插在 2 和 3 之间，得到 [2, 4, 3, 5]——正是 doctest 里那个「看起来没排序」的答案。 如果你算出的是 [2, 3, 4, 5]，说明你不小心按值排序了。

5. Q5 remove_first 与 sort：用递归排序

这一题分两半：先写一个删除工具 remove_first，再用它递归地实现排序 sort。 两半都必须用递归——尤其 sort，题面明确写着 Use recursion!。

5.1 remove_first：题目要什么

输入列表 lst 和一个数 elem，返回一个新列表，其中 elem 的第一次出现被删掉， 其余原样保留。

>>> remove_first([3, 4] , 3)
[4]
>>> remove_first([3, 4, 3] , 3)
[4, 3]
>>> remove_first([2, 4] , 3)
[2, 4]
>>> remove_first([] , 0)
[]

四个 doctest 恰好把所有边界都点到了：

5.2 remove_first：怎么想到的

「只删第一个」这个要求，用循环写反而别扭：你得记一个「删过没有」的标志位， 删完还要继续把剩下的抄进结果。而递归的思路是只看开头一个元素，其余交给自己：

5.3 remove_first：代码

def remove_first(lst: list, elem: int) -> list:
    if lst == []:
        return []
    elif lst[0] == elem:
        # Found the first appearance: drop it and keep the rest as is.
        return lst[1:]
    else:
        # Keep the first item and remove elem from the rest.
        return [lst[0]] + remove_first(lst[1:], elem)

5.4 remove_first：验证

调用 A: remove_first([3, 4, 3], 3)
  lst == [] ?    否
  lst[0] == 3 ?  是（lst[0] 就是 3）
  → 返回 lst[1:] = [4, 3]        ← 一次递归都没发生

结果：[4, 3]   ← 与 doctest 一致，第二个 3 完好保留

再看一个需要真正递归的：

调用 A: remove_first([2, 4], 3)
  lst == [] ? 否；lst[0] = 2 ≠ 3
  → 返回 [2] + remove_first([4], 3)

      调用 B: remove_first([4], 3)
        lst == [] ? 否；lst[0] = 4 ≠ 3
        → 返回 [4] + remove_first([], 3)

            调用 C: remove_first([], 3)
              lst == [] ? 是 → 返回 []

        回到 B: [4] + [] = [4]，返回 [4]

  回到 A: [2] + [4] = [2, 4]，返回 [2, 4]   ← 与 doctest 一致

这一路推演展示了「没找到目标」的情形：递归一路走到空列表， 回代时把每一层留下的 lst[0] 依次拼回去，最后得到一个和输入一模一样（但对象是新的）的列表。

elif lst[0] == elem:
    return remove_first(lst[1:], elem)     # 错

5.5 sort：题目要什么

输入列表 lst，返回它排好序（升序）的版本。必须用递归，题面提示用刚写好的 remove_first 和内建的 min。

>>> sort([6, 2, 5])
[2, 5, 6]
>>> sort([2, 3])
[2, 3]
>>> sort([3])
[3]
>>> sort([])
[]

5.6 sort：怎么想到的

「排序」听起来是个大工程，但递归的问法永远是同一句：结果的第一个元素是什么？剩下的是什么？

排好序的列表，第一个元素显然是整个列表里最小的那个——这不需要任何算法， min(lst) 直接给你。那么剩下的部分呢？就是「把这个最小值拿掉之后，剩下那些数排好序」。 而「排好序」正是 sort 自己。于是：

递归基：空列表已经是排好序的，返回 []。为什么递归一定会到空列表？因为 remove_first 每次确实删掉一个元素（min(lst) 一定在 lst 里，命中分支必然触发）， 所以每层递归列表长度严格减一。

为什么必须用 remove_first 而不是「过滤掉所有等于 min 的元素」

假如你写成 [x for x in lst if x != smallest]，那么 sort([2, 2, 5]) 会返回 [2, 5]—— 少了一个 2。排序不能丢元素，重复值必须原样保留。remove_first 一次只删一个，正好合适。 虽然本题 doctest 里没有重复值，但 ok 的隐藏测试和你自己的良心都会检查这一点。

5.7 sort：代码

def sort(lst: list) -> list:
    if lst == []:
        return []
    smallest = min(lst)
    # The smallest element goes first; sort whatever is left over.
    return [smallest] + sort(remove_first(lst, smallest))

注意 sort 没有修改 lst：min 只读，remove_first 返回新列表，最外层的 + 也造新列表。 所以调用 sort(t) 之后 t 还是原来的顺序。这和 Python 自带的 list.sort()（原地排序，返回 None） 是两种不同的设计，别混淆。

5.8 sort：验证

调用 A: sort([6, 2, 5])
  lst == [] ? 否
  smallest = min([6, 2, 5]) = 2
  remove_first([6, 2, 5], 2)
      → lst[0] = 6 ≠ 2 → [6] + remove_first([2, 5], 2)
                              → lst[0] = 2 == 2 → 返回 [5]
      → [6] + [5] = [6, 5]
  返回 [2] + sort([6, 5])

      调用 B: sort([6, 5])
        smallest = min([6, 5]) = 5
        remove_first([6, 5], 5)
            → 6 ≠ 5 → [6] + remove_first([5], 5)
                          → 5 == 5 → 返回 []
            → [6] + [] = [6]
        返回 [5] + sort([6])

            调用 C: sort([6])
              smallest = min([6]) = 6
              remove_first([6], 6) → 6 == 6 → 返回 []
              返回 [6] + sort([])

                  调用 D: sort([])
                    lst == [] → 返回 []

              回到 C: [6] + [] = [6]，返回 [6]

        回到 B: [5] + [6] = [5, 6]，返回 [5, 6]

  回到 A: [2] + [5, 6] = [2, 5, 6]，返回 [2, 5, 6]   ← 与 doctest 一致

看这个推演的形状：递归下降时列表越来越短（3 → 2 → 1 → 0）， 回代时结果越来越长（[] → [6] → [5, 6] → [2, 5, 6]）。 每一层贡献一个元素，而且贡献的正好是这一层的最小值。 最外层贡献的是全局最小 2，所以它排在最前——递归的正确性就是这么保证的。

def sort(lst):
    smallest = min(lst)        # 错：lst 为空时直接炸
    if lst == []:
        return []

return [smallest] + sort(lst)     # 错：无限递归

6. Q6 make_onion：能不能在 limit 步内走到

题目要什么

make_onion(f, g) 接收两个单参数函数 f 和 g，返回一个新函数 can_reach(x, y, limit)。这个新函数回答一个是非题：从 x 出发，最多用 limit 次 f 或 g 的调用，能不能得到 y？能就返回 True，不能就 False。

「洋葱（onion）」这个名字来自结果表达式的形状：f(g(g(f(x))))——一层裹一层。 每一层可以自由选 f 或 g，总层数不超过 limit。

>>> up = lambda x: x + 1
>>> double = lambda y: y * 2
>>> can_reach = make_onion(up, double)
>>> can_reach(5, 25, 4)      # 25 = up(double(double(up(5))))
True
>>> can_reach(5, 25, 3)      # Not possible
False
>>> can_reach(1, 1, 0)      # 1 = 1
True
>>> add_ing = lambda x: x + "ing"
>>> add_end = lambda y: y + "end"
>>> can_reach_string = make_onion(add_ing, add_end)
>>> can_reach_string("cry", "crying", 1)      # "crying" = add_ing("cry")
True
>>> can_reach_string("un", "unending", 3)     # "unending" = add_ing(add_end("un"))
True
>>> can_reach_string("peach", "folding", 4)   # Not possible
False

doctest 里藏着几条必须读出来的规则：

怎么想到的

第一步：认出这是「返回函数」的高阶函数题

make_onion 返回的东西要能被这样用：can_reach = make_onion(up, double)， 之后 can_reach(5, 25, 4)。所以 make_onion 的函数体必须是 「定义一个内部函数，然后 return 那个函数名」——注意是 return can_reach， 不带括号。带括号就成了「调用它并返回结果」，可你这会儿根本没有 x, y, limit 可传。

为什么内部函数能用到 f 和 g？因为 can_reach 是在 make_onion 的帧里定义的， 它的 parent 就是那个帧，f、g 在里面。这就是闭包： 即使 make_onion 早已返回，那个帧因为被 can_reach 记着，依然活着。

第二步：把「能不能到达」翻译成递归

先别急着写代码，先问自己：站在 x 这个位置，我下一步能干什么？

只有两个选择：调用 f，走到 f(x)；或者调用 g，走到 g(x)。 无论走哪条，剩余可用次数都少 1。所以：

这个思路的漂亮之处在于：你完全不需要知道 f 和 g 是干什么的。 不管它们是加 1、翻倍，还是接字符串，「下一步只能是 f 或 g」这个结构永远成立。 所以 "peach" 那个例子里，代码照样老老实实地把 16 条路径（4 步，每步 2 选 1）全走一遍， 发现没有一条得到 "folding"，返回 False。

第三步：两个 base case 的顺序

递归必须有出口。这题有两个：

• 成功出口：x == y，返回 True。
• 失败出口：次数用光了还没等于 y，返回 False。

失败出口怎么写？两个候选：limit == 0 还是 limit < 0？这里要仔细想。

考虑 can_reach(5, 6, 1)，即「一步之内从 5 到 6」，答案应该是 True（up(5) = 6）。

若写 if limit == 0: return False  且把它放在 x == y 之前：
    第一层：limit = 1，不为 0；x = 5 ≠ 6
            → can_reach(6, 6, 0) or can_reach(10, 6, 0)
    第二层：limit == 0 → 立刻返回 False
            但此时 x = 6 就是 y！答案被错杀，返回 False   ✗

若写 if limit < 0: return False，放在最前：
    第一层：limit = 1，不小于 0；x = 5 ≠ 6
            → can_reach(6, 6, 0) or ...
    第二层：limit = 0，不小于 0；x = 6 == y → 返回 True   ✓

结论：用 limit < 0。它的含义是「已经多花了一次调用」， 而 limit == 0 只是「刚好花完，但当前这个值还没检查过」。 当然，另一种等价的正确写法是把 x == y 判断放在 limit == 0 之前， 但 limit < 0 的版本对分支顺序不敏感，更稳。

代码

def make_onion(f, g):
    def can_reach(x, y, limit: int) -> bool:
        if limit < 0:
            # Ran out of calls without ever hitting y.
            return False
        elif x == y:
            return True
        else:
            # Peel one more layer: the next call is either f or g.
            return can_reach(f(x), y, limit - 1) or can_reach(g(x), y, limit - 1)
    return can_reach

环境图：can_reach = make_onion(up, double) 之后发生了什么

全局帧 Global
    up        → func λ(x): x + 1   [parent = Global]
    double    → func λ(y): y * 2   [parent = Global]
    make_onion→ func make_onion(f, g) [parent = Global]
    can_reach → func can_reach(x, y, limit) [parent = f1]   ← 注意 parent

f1: make_onion    [parent = Global]
    f  → 上面那个 up 函数
    g  → 上面那个 double 函数
    can_reach → func can_reach(x, y, limit) [parent = f1]
    返回值 → 那个 can_reach 函数

调用 can_reach(5, 25, 4) 时新开的帧：
f2: can_reach     [parent = f1]      ← parent 是 f1，不是 Global
    x = 5, y = 25, limit = 4
    体内查 f  → f2 没有 → 去 parent f1 → 找到 up      ✓
    体内查 can_reach → f2 没有 → 去 f1 → 找到          ✓

这张图解释了两件容易糊涂的事。第一，f 和 g 明明是 make_onion 的形参， 为什么 make_onion 都返回了它们还在？因为 can_reach 的 parent 指着 f1，f1 就不能被丢掉。 第二，can_reach 内部递归调用 can_reach，查的是哪个名字？ 从 f2 出发查 parent f1，在 f1 里找到——不是全局那个。 即使你在全局把 can_reach 重新绑定成别的东西，递归照样正确，因为它走的是 f1 这条链。

验证

完整展开 can_reach(5, 25, 4) 的调用树会有 2⁴ = 16 个叶子，太大。 但因为 or 短路，实际走的路径少得多。我们沿着会成功的那条路追， 同时标出在它之前被试过并失败的分支。f 是 up（+1），g 是 double（×2）。

can_reach(5, 25, 4)
  limit=4 不小于 0；5 ≠ 25
  → can_reach(up(5)=6, 25, 3)  or  can_reach(double(5)=10, 25, 3)

  先算左边 can_reach(6, 25, 3)
    6 ≠ 25 → can_reach(7, 25, 2) or can_reach(12, 25, 2)

    左边 can_reach(7, 25, 2)
      7 ≠ 25 → can_reach(8, 25, 1) or can_reach(14, 25, 1)
      can_reach(8, 25, 1)  → 8≠25 → can_reach(9,25,0) or can_reach(16,25,0)
                                    9≠25，limit-1=-1 → 两个孙子都 False → False
                                    16≠25 同理 → False        ⇒ False
      can_reach(14, 25, 1) → 14≠25 → can_reach(15,25,0)=False
                                     can_reach(28,25,0)=False ⇒ False
      ⇒ can_reach(7, 25, 2) = False

    右边 can_reach(12, 25, 2)
      12 ≠ 25 → can_reach(13, 25, 1) or can_reach(24, 25, 1)
      can_reach(13, 25, 1) → 13≠25 → can_reach(14,25,0)=False
                                      can_reach(26,25,0)=False ⇒ False
      can_reach(24, 25, 1) → 24≠25 → can_reach(up(24)=25, 25, 0)
                                        limit=0 不小于 0，25 == 25 → True  ★
                             or 短路，double(24) 那支根本不算 ⇒ True
      ⇒ can_reach(12, 25, 2) = True

    ⇒ can_reach(6, 25, 3) = True
  左边已 True，or 短路，can_reach(10, 25, 3) 根本不执行
  ⇒ 返回 True                                  ← 与 doctest 一致

把成功的那条路径倒着读出来：5 →(up) 6 →(double) 12 →(double) 24 →(up) 25， 写成表达式就是 up(double(double(up(5))))，正是 doctest 注释里那一行，用了 4 次调用。

再看 can_reach(5, 25, 3) 为什么是 False：三步之内，从 5 出发能到达的所有值是

这 15 个值里没有 25，所以返回 False。注意第 3 步里出现了重复的 12 （up(up(double(5))) 之外还有别的路径撞上同一个值）——朴素的树递归会把重复的分支各算一遍， 这是它效率低的原因，但正确性不受影响。

最后核一下 can_reach(1, 1, 0)：limit = 0 不小于 0，跳过第一个分支； x == y 成立，直接返回 True。零次调用也算「用最多 0 次调用到达」，这正是我们前面辨析 limit < 0 与 limit == 0 时保住的那个语义。

return can_reach(f(x), y, limit-1) and can_reach(g(x), y, limit-1)   # 错

7. Q7（选做）make_func_repeater：把函数应用 n 次

题目要什么

make_func_repeater(f, x) 接收一个单参数函数 f 和一个初值 x， 返回一个新函数。这个新函数接收一个整数 n，返回把 f 作用在 x 上 n 次的结果， 也就是 $f^n(x)$。题面要求：必须用递归。

>>> increment_repeater = make_func_repeater(lambda x: x + 1, 1)
>>> increment_repeater(2) #same as f(f(x))
3
>>> increment_repeater(5)
6

两个 doctest 需要仔细读。f 是加一，x 是 1。

• increment_repeater(2) = f(f(1)) = f(2) = 3。注释 same as f(f(x)) 直接给出了定义。
• increment_repeater(5) = f(f(f(f(f(1))))) = 6。

第二个 doctest 悄悄规定了一件重要的事：x 不会被累积修改。 如果第一次调用把 x 从 1 改成了 3，那第二次调用 increment_repeater(5) 就会得到 8 而不是 6。 所以每次调用都必须从原始的 x 重新开始。

还有个没写在 doctest 里但必须成立的边界：n = 0 时应返回 x 本身（作用零次）。 这也正是递归基。

题面给的骨架已经把结构框死了：

    def repeat(____):
        if ____:
            return ____
        else:
            return ____
    return ____

怎么想到的

这题的关键在于把它跟 HW 1 里那道类似的题（用循环写的 repeater）对照着看。 题面自己提示了这一点：This is very similar to a homework problem, but recursive.

循环版本大概是「while n > 0: x = f(x); n = n - 1」，靠一个变量反复被重新赋值来累积。 递归版本不需要任何变量被修改，它靠的是一个恒等式：

为什么拆的时候要把 f 放在外面（f(repeat(n-1))）而不是里面？ 其实两种都对：f 作用 n 次，先做哪次都一样，因为是同一个函数反复作用。 但写成 f(repeat(n - 1)) 更自然，因为 repeat 的参数只能是数字（次数）， 不能同时改起点——起点 x 是固定在闭包里的。这一点是本题与常规递归的区别所在。

为什么这不是「自引用（self-reference）」

题面特意提醒要和自引用对比。所谓自引用是这样的写法：函数返回一个新函数， 调用方要写 rep(1)(1)(1) 那样连续调用才能累积效果。这里不是—— repeat 返回的是一个最终的值（比如整数 3），一次 increment_repeater(2) 就把全部计算做完了。区别在两处：

代码

def make_func_repeater(f, x: int):
    def repeat(n: int):
        if n == 0:
            # Applying f zero times just gives back the starting value.
            return x
        else:
            # Apply f once on top of the result of n - 1 applications.
            return f(repeat(n - 1))
    return repeat

验证

设 f = lambda x: x + 1，x = 1，跑 increment_repeater(2)。

Global
    make_func_repeater  → func
    increment_repeater  → func repeat(n) [parent = f1]

f1: make_func_repeater  [parent = Global]
    f = λ(x): x + 1
    x = 1
    repeat → func repeat(n) [parent = f1]

调用 repeat(2)   （新帧 f2，parent = f1）
  n = 2 ≠ 0
  → 返回 f(repeat(1))，先算 repeat(1)

      调用 repeat(1)   （新帧 f3，parent = f1）
        n = 1 ≠ 0
        → 返回 f(repeat(0))，先算 repeat(0)

            调用 repeat(0)   （新帧 f4，parent = f1）
              n == 0 → 返回 x
              f4 里没有 x → 去 parent f1 查 → x = 1
              返回 1

        回到 f3: f(1)，f 在 f1 里查到，是 λ(x): x+1
                 f(1) = 2，返回 2

  回到 f2: f(2) = 3，返回 3            ← 与 doctest 一致

注意每一个 repeat 帧的 parent 都是 f1，不是上一层的 repeat 帧。 这是因为「parent 由函数定义在哪里决定，不由调用在哪里决定」。 所以四层递归查 x 时，查到的都是同一个 f1 里的 x = 1。

再跑 increment_repeater(5)：它开一批全新的帧，最底层照样从 f1 拿到 x = 1， 然后加五次一得 6——第一次调用没有留下任何痕迹。如果实现里改过 x，这里就会是 8。

8. Q8（选做）ten_pairs：数出所有和为十的数位对

题目要什么

给一个正整数 n，数出它里面有多少个「十对」：一对数位，两者相加等于 10。

>>> ten_pairs(7823952) # 7+3, 8+2, and 8+2
3
>>> ten_pairs(55055)
6
>>> ten_pairs(9641469) # 9+1, 6+4, 6+4, 4+6, 1+9, 4+6
6

题面额外给了两条规则，读漏任何一条答案都会错：

• 一个数位可以参与多个十对。看 7823952：数位是 7、8、2、3、9、5、2。 那个 8 同时和第一个 2、第二个 2 各配成一对，算两对。 所以总数是 7+3、8+2、8+2 共 3 对。
• 一个 5 不能和自己配对。5+5 = 10 需要两个 5。55055 有四个 5， 任取两个都成一对，共 $\binom{4}{2} = 6$ 对，正是第二个 doctest 的答案。 但如果只有一个 5，它配不成任何对。

还有一条硬性约束：禁止使用循环。doctest 里那句 check(SOURCE_FILE, 'ten_pairs', ['While', 'For']) 会去扫描源码的语法树， 发现 while 或 for 就判失败。所以只能递归。

题面还建议先写一个辅助函数 count_digit(n, digit)，返回 digit 在 n 里出现了几次：

>>> count_digit(55055, 5) # digit 5 appears 4 times in 55055
4

怎么想到的

第一次尝试：按「配对」去想，然后卡住

直觉的做法是「取出所有数位，两两比较」。但这需要两层嵌套循环，而循环被禁了； 写成两层递归也很别扭，因为你得同时维护两个游标在同一个数上移动。这条路能走通但很痛苦。

换个问法：让每个数位只负责「它前面的」

如果每一对都被数两次（a 配 b、b 配 a），结果就会翻倍。要避免重复， 标准手法是给配对定一个方向：规定每一对由它靠右的那个数位来统计， 只往左边找搭档。这样每对恰好被数一次。

于是问题被拆成了漂亮的两块：

顺带解决了「5 不能和自己配对」的问题：count_digit 数的是 rest 里的 5， 而当前这个 5 已经被 n % 10 摘出去了，不在 rest 里，所以绝不会自己配自己。 这个正确性是「只往左看」这个方向约定白送的，不需要额外写任何判断。

count_digit 怎么递归

数一个数位出现几次，是最标准的数位递归：看最后一位是不是目标，是就 +1， 然后把问题交给 n // 10。递归基是 n == 0——数位剥完了，返回 0。

代码

def ten_pairs(n: int) -> int:
    if n < 10:
        # A single digit cannot pair with anything.
        return 0
    last_digit = n % 10
    rest = n // 10
    # Every earlier digit equal to 10 - last_digit forms a ten-pair with it,
    # plus all the ten-pairs that live entirely inside the earlier digits.
    return count_digit(rest, 10 - last_digit) + ten_pairs(rest)


def count_digit(n: int, digit: int) -> int:
    if n == 0:
        return 0
    elif n % 10 == digit:
        return 1 + count_digit(n // 10, digit)
    else:
        return count_digit(n // 10, digit)

验证

先验 count_digit(55055, 5)：

count_digit(55055, 5)  n%10 = 5 == 5 → 1 + count_digit(5505, 5)
count_digit(5505, 5)   n%10 = 5 == 5 → 1 + count_digit(550, 5)
count_digit(550, 5)    n%10 = 0 ≠ 5  →     count_digit(55, 5)
count_digit(55, 5)     n%10 = 5 == 5 → 1 + count_digit(5, 5)
count_digit(5, 5)      n%10 = 5 == 5 → 1 + count_digit(0, 5)
count_digit(0, 5)      n == 0        → 0

回代：0 → 1 → 2 → 2 → 3 → 4
结果：4                              ← 与 doctest 一致

再验主函数 ten_pairs(55055)。数位从右到左是 5、5、0、5、5。

ten_pairs(55055)
  last = 5, rest = 5505
  count_digit(5505, 5) = 3        ← 5505 里有三个 5
  → 3 + ten_pairs(5505)

  ten_pairs(5505)
    last = 5, rest = 550
    count_digit(550, 5) = 2       ← 550 里有两个 5
    → 2 + ten_pairs(550)

    ten_pairs(550)
      last = 0, rest = 55
      count_digit(55, 10) = 0     ← 找「等于 10 的数位」，找不到
      → 0 + ten_pairs(55)

      ten_pairs(55)
        last = 5, rest = 5
        count_digit(5, 5) = 1     ← 剩下那个 5
        → 1 + ten_pairs(5)

        ten_pairs(5)
          5 < 10 → 返回 0

        回到 ten_pairs(55):  1 + 0 = 1
      回到 ten_pairs(550):   0 + 1 = 1
    回到 ten_pairs(5505):    2 + 1 = 3
  回到 ten_pairs(55055):     3 + 3 = 6

结果：6                            ← 与 doctest 一致

用组合数核对一下：四个 5 里任选两个组成一对，$\binom{4}{2} = 6$。 而推演里每一层贡献的 3、2、0、1 加起来正好是 6—— 这不是巧合，3 + 2 + 1 = 6 就是 $\binom{4}{2}$ 的「每个 5 与它左边的 5 配对」的算法。 那个 0 是数位 0 那一层贡献的，它配不成任何对。

最后核 ten_pairs(7823952)，只列每层贡献：

合计 1 + 0 + 0 + 1 + 1 + 0 = 3，与 doctest 一致。 对应的三对正是注释里的 8+2（末位那个 2）、7+3、8+2（中间那个 2）。

9. ok 的验证情况

在 labs/lab03/ 目录下运行 python3 ok --local，结果是 6 个测试用例全部通过，本次作业全部题目通过，没有跳过、没有伪造。

关于 WWPD 题的答案来源需要说明：官方测试文件里，这类题的答案在未解锁状态下是 HMAC 哈希，不能直接读。本仓库的做法是真的把每一行输入交给 Python 执行， 拿到真实输出后再与官方哈希比对——对得上才算解开。 所以本页第 1 节和第 3 节里写的每一个显示结果，都是被官方哈希校验过的，不是凭印象填的。

整份作业回顾

这次真正学到的不是六个函数，而是几套能反复用的思维方法。

一、递归的三个必答问题

本次每一道递归题，落到纸上都是同样三问。写不出代码时，逐条问自己：

二、「造新的」而不是「改旧的」

本次所有列表操作都用 + 和切片，一次 append、pop、sort() 都没用。 这不是巧合。只要函数从不修改传进来的对象，它就没有副作用， 你可以放心地在递归里反复调用它而不担心互相干扰。 这也是 flatten 那条 deep 保持不变的 doctest 想让你养成的习惯。 下一讲讲可变性（mutability）时，你会看到不遵守这条会出什么事。

三、分支的形状就是问题的形状

四、遇到「不知道要循环几层」就用递归

flatten 是最典型的例子：嵌套有几层是运行时才知道的， 所以代码里写死几层循环必然失败。凡是碰到这种「深度由数据决定」的结构 （后面的树、链表、Scheme 的嵌套表达式全都是），递归是唯一的写法。

五、返回函数的函数，parent 由定义位置决定

Q6 和 Q7 都是「make_XXX 返回一个内部函数」的形状。这类题的两个固定考点：

• return 内部函数名时不加括号。
• 内部函数每次被调用都开新帧，但新帧的 parent 永远是定义它的那个帧， 所以外层的 f、g、x 一直可见且不变。