HW 5：链表、效率与 Schemeok 11 项通过

0. 这份作业在练什么

HW 5 表面上是三个互不相干的话题拼在一起，实际上它们被同一根线串着：一个数据结构的形状，决定了你能写出什么样的代码，也决定了这段代码要跑多久。

链表（linked list）是这门课里第一个「递归定义的数据结构」——它的定义里出现了它自己：一个链表要么是空的，要么是「一个值 + 一个链表」。定义是递归的，处理它的代码自然也就是递归的。Q1、Q2 就是在把这句话练成肌肉记忆，而且是从两个相反的方向练：Q1 只造新的、不碰旧的，Q2 只改旧的、不造新的。这两种模式是后面所有链表题的母版。

Q3 换了一个提问方式。之前所有题目问的都是「对不对」，Q3 第一次问「快不快」。一个能返回正确答案但要跑三个小时的 is_prime，在这门课的评分标准里是错的。你需要学会一件事：看着一段代码，估算出它的操作次数随输入怎么增长，并且知道怎么把这个增长阶降下来。

Q4–Q6 是 Scheme 的入门。别把它当成「学一门新语言」——它其实是把你已经懂的求值规则（算子先求值、算子数从左到右求值、然后 apply）用一套没有语法糖的写法重新表达一遍。Scheme 里没有 while、没有 for、没有中缀运算符，你只剩下递归和调用表达式。这种「什么都没有」恰恰是它的价值：它逼你把控制流全部还原成函数调用。

关于验证状态

本仓库中 hw/hw05/ 目录下的代码在本地跑 python3 ok --local，结果是 11 个测试用例全部通过，六道题无一遗漏。下面贴出的每一段代码都与该目录里的真实文件逐字一致。

先把 Link 类摆在这里

Q1、Q2 都建立在这个类之上，后面会反复引用它的每一行，所以先完整读一遍：

class Link:
    """A linked list.

    >>> s = Link(1)
    >>> s.first
    1
    >>> s.rest is Link.empty
    True
    """
    empty = ()

    def __init__(self, first, rest=empty):
        assert rest is Link.empty or isinstance(rest, Link)
        self.first = first
        self.rest = rest

    def __repr__(self):
        if self.rest is not Link.empty:
            rest_repr = ', ' + repr(self.rest)
        else:
            rest_repr = ''
        return 'Link(' + repr(self.first) + rest_repr + ')'

    def __str__(self):
        string = '('
        while self.rest is not Link.empty:
            string += str(self.first) + ' '
            self = self.rest
        return string + str(self.first) + ')'

三个地方值得单独说：

1）empty = () 是一个类属性，值是空元组。为什么用空元组而不是 None？因为空元组是唯一的、不可变的，而且在布尔语境下为假。更重要的是它是类属性，所有 Link 实例共享同一个 Link.empty，所以可以放心用 is 判断。

2）__init__ 里的 assert 是一道护栏。它规定 rest 只能是 Link.empty 或另一个 Link。这意味着你不能写 Link(1, 2)——链表的「尾巴」必须还是链表。这条约束正是「链表是递归定义的」在代码层面的体现。注意 first 没有任何约束，所以 first 可以是一个 Link，这就是 Q2 里「嵌套链表」的来源。

3）__repr__ 与 __str__ 显示的东西完全不同。这一点在 doctest 里会造成大量困惑：

__str__ 用的是 Scheme 风格的括号记法：外层一对括号，元素用空格分隔，嵌套链表就再套一层括号。这个记法在 Q2 的 doctest 里到处都是——(3 (4) 5 6) 表示一个长度为 4 的链表，它的第二个元素是一个只含 4 的子链表。看懂这个记法是做 Q2 的前提。

1. 拼接链表 add_links

题目要什么

给两个链表 link1 和 link2，返回一个新的链表，内容是 link1 的所有元素后面跟着 link2 的所有元素。

def add_links(link1: Link, link2: Link) -> Link:
    """Adds two Links, returning a new Link

    >>> l1 = Link(1, Link(2))
    >>> l2 = Link(3, Link(4, Link(5)))
    >>> new = add_links(l1, l2)
    >>> print(new)
    (1 2 3 4 5)
    >>> new2 = add_links(l2,l1)
    >>> print(new2)
    (3 4 5 1 2)
    """

题面里有几句话必须抠字眼：

• "returning a new Link"——返回新链表。虽然题目没有明说「不许改原链表」，但从 doctest 能看出端倪：第二次调用 add_links(l2, l1) 用的还是同样的 l1 和 l2，结果是 (3 4 5 1 2)。如果第一次调用时你把 l1 的最后一个节点的 rest 直接指向了 l2，那么 l1 就已经变成 (1 2 3 4 5) 了，第二次调用会得到 (3 4 5 1 2 3 4 5)，甚至因为 l2 尾部指回自己而变成一个环，print 会死循环。doctest 的第二行是在专门抓这个坑。
• "You may assume that the input list is shallow"——输入是浅的，元素本身不会是链表。所以你不用像 Q2 那样递归进入元素内部。
• "You may not assume that the input lists are of the same length"——两个链表长度可以不同（doctest 里就是 2 和 3）。这排除了「同时遍历两个链表」的错误思路。
• 边界情况：其中一个（或两个）链表为空。doctest 没有覆盖，但递归写法必须处理，否则 Link.empty.first 会报 AttributeError: 'tuple' object has no attribute 'first'。

怎么想到的

先说一条弯路，因为大部分人第一反应都是它。

def add_links(link1, link2):
    p = link1
    while p.rest is not Link.empty:
        p = p.rest
    p.rest = link2        # 把 link2 接到 link1 尾巴上
    return link1

知道不能改原表之后，思路就只剩一条：把 link1 的每个节点都复制一份，复制到头之后，接上 link2（或者继续复制 link2）。

接下来的关键提问是：怎么把「复制并拼接」写成递归？递归的套路永远是同一句话：假设 add_links 对更小的输入已经能正确工作，我怎么用它的结果拼出当前答案。

return Link(link1.first, add_links(link1.rest, link2))

现在只差 base case：link1 空了怎么办？此时应该轮到 link2。这里又有一个选择点：

• 方案 A：if link1 is Link.empty: return link2。写起来最短，但它直接把 link2 本身接在了新链表尾部——返回的链表后半段和 link2 是同一批节点（共享，aliasing）。这在本题的测试下能通过（因为没人去改结果），但它不是严格意义上的「全新链表」。
• 方案 B：继续复制 link2 的每个节点。彻底做到「不共享任何节点」。

本仓库用的是方案 B，代价是多写两行，收益是语义干净：返回的链表和两个输入表完全没有共享节点，之后无论谁改哪个都不会互相影响。

代码逐行讲

def add_links(link1: Link, link2: Link) -> Link:
    if link1 is Link.empty and link2 is Link.empty:
        return Link.empty
    elif link1 is Link.empty:
        # link1 is used up, so keep copying the elements of link2.
        return Link(link2.first, add_links(Link.empty, link2.rest))
    else:
        # Copy the current element of link1, then build the rest.
        return Link(link1.first, add_links(link1.rest, link2))

第 2–3 行：两个都空，结果只能是空链表。这是唯一的终止出口——所有递归分支最后都会收敛到这里。注意返回的是 Link.empty 而不是 None：因为它要被塞进上一层的 Link(x, ...) 的 rest 参数，而 __init__ 里的 assert 只接受 Link.empty 或 Link。返回 None 会直接触发 AssertionError。

第 4–6 行：link1 空了但 link2 还有货。此时复制 link2 的当前元素，然后递归处理 link2.rest。为什么第一个参数写死 Link.empty？因为一旦 link1 用完了，它在后面所有层都是空的，直接传空表让下一层继续走这个分支即可。

第 7–9 行：link1 还有货（不管 link2 是空是满）。复制 link1.first，递归处理 (link1.rest, link2)。注意 link2 一动不动地往下传——它要等 link1 彻底走完才轮到。

三个分支合起来恰好覆盖了 (空, 空) / (空, 非空) / (非空, 任意)，没有遗漏也没有重叠。

验证：手动展开 add_links(l1, l2)

取 l1 = Link(1, Link(2))，l2 = Link(3, Link(4, Link(5)))。把递归真的一层层展开：

调用 1: add_links((1 2), (3 4 5))
        link1 非空 → 走 else
        = Link(1, add_links((2), (3 4 5)))
                    ↓ 需要先算里面这个

调用 2: add_links((2), (3 4 5))
        link1 非空 → 走 else
        = Link(2, add_links(empty, (3 4 5)))
                    ↓

调用 3: add_links(empty, (3 4 5))
        link1 空、link2 非空 → 走 elif
        = Link(3, add_links(empty, (4 5)))
                    ↓

调用 4: add_links(empty, (4 5))
        = Link(4, add_links(empty, (5)))
                    ↓

调用 5: add_links(empty, (5))
        = Link(5, add_links(empty, empty))
                    ↓

调用 6: add_links(empty, empty)
        两个都空 → 走第一个 if
        返回 Link.empty          ← 触底，开始回代

现在从最深处往回代，每一层把自己的 Link(...) 真正建出来：

print(new) 调用 __str__，输出 (1 2 3 4 5)。与 doctest 一致。

关键在于：整个过程中 l1 和 l2 的任何一个 first 或 rest 都没有被赋值过，只被读取过。所以第二行 doctest add_links(l2, l1) 面对的仍是原封不动的 (3 4 5) 和 (1 2)，按同样的展开会得到 (3 4 5 1 2)。

谁指向谁

调用结束后内存里有三条独立的链：

l1  →  [1|•] → [2|/]                       （原样未动，2 个节点）

l2  →  [3|•] → [4|•] → [5|/]               （原样未动，3 个节点）

new →  [1|•] → [2|•] → [3|•] → [4|•] → [5|/]
       ↑ 全部是 add_links 里 Link(...) 新造的 5 个节点，
         与上面两条链没有任何一个节点是同一个对象

（•表示 rest 指向下一个节点，/ 表示 rest is Link.empty）

可选挑战：允许嵌套输入

题面给了一个 Challenge：如果输入链表的元素本身可能是链表，怎么办？提示是用内置的 type 函数。思路是在复制元素时判断一下：如果 link1.first 是 Link，就递归地把它也复制一份（add_links(link1.first, Link.empty) 就是「复制这条子链」），否则直接拿值。这一问不计分，本仓库提交的是上面那版浅拷贝实现；点出来是因为它和 Q2 的「元素可能是链表」是同一个观察角度。

2. 就地深层映射 deep_map_mut

题目要什么

写 deep_map_mut(func, s)，把链表 s 里的每个元素替换成 func(元素)。如果某个元素本身是一个链表，就递归进去，对它内部的元素做同样的事。函数返回 None，效果全靠就地修改。

硬性约束写在标题里：Does NOT create new Links。你的代码里一次都不能出现 Link(...) 构造器调用。

>>> link1 = Link(3, Link(Link(4), Link(5, Link(6))))
>>> square = lambda x: x * x
>>> print(link1)
(3 (4) 5 6)
>>> link2 = Link(1, Link(Link(Link(2, Link(3))), Link(4)))
>>> double = lambda x: x * 2
>>> print(link2)
(1 ((2 3)) 4)
>>> # Disallow the use of making new Links before calling deep_map_mut
>>> Link.__init__, hold = lambda *args: print("Do not create any new Links."), Link.__init__
>>> try:
...     deep_map_mut(square, link1)
...     deep_map_mut(double, link2)
... finally:
...     Link.__init__ = hold
>>> print(link1)
(9 (16) 25 36)
>>> print(link2)
(2 ((4 6)) 8)

先把 doctest 那段黑魔法看懂

中间那几行不是普通代码，它是一个检查装置，很多人被它吓住，其实拆开只有三步：

Link.__init__, hold = lambda *args: print("Do not create any new Links."), Link.__init__

这是一个多重赋值。Python 先把右边整体求值，得到元组 (那个 lambda, 原来的 Link.__init__)，然后再左右对应地绑定。所以 hold 拿到的是原始的 __init__（右边在赋值发生前就已经求好了值），而 Link.__init__ 被换成了一个只会打印警告、什么都不初始化的 lambda。

try / finally 的作用是：不管你的函数有没有抛异常，finally 都会把真正的 __init__ 从 hold 还回去，免得污染后面的测试。这也是 hold 存在的唯一理由。

把 doctest 里的括号记法翻译成图

link1 = Link(3, Link(Link(4), Link(5, Link(6))))，打印出来是 (3 (4) 5 6)。逐节点看：

link1 → [ 3 |•] → [ • |•] → [ 5 |•] → [ 6 |/]
                    ↓
                  [ 4 |/]

节点 1：first = 3        （普通数）
节点 2：first = Link(4)  （是个链表！打印成 (4)）
节点 3：first = 5
节点 4：first = 6

link2 = Link(1, Link(Link(Link(2, Link(3))), Link(4)))，打印成 (1 ((2 3)) 4)，嵌套更深一层：

link2 → [ 1 |•] → [ • |•] → [ 4 |/]
                    ↓
                  [ • |/]
                    ↓
                  [ 2 |•] → [ 3 |/]

第二个元素是「一个链表，它唯一的元素又是一个链表 (2 3)」
所以打印成 ((2 3))

期望结果 (2 ((4 6)) 8) 说明：double 被作用到了 1, 2, 3, 4 这四个真正的数上，而没有被作用到中间那两层链表节点上。这就是「deep」的含义——遇到链表要钻进去，不是把链表整个丢给 func。

怎么想到的

先想「不许创建新 Link」这条约束到底封死了什么。它封死了「造一条新链再返回」的路，逼你只能用属性赋值来干活。Link 对象只有两个属性可以赋值：

第三行值得多说一句，因为它是最常见的错误直觉：在函数里写 s = 什么什么，只是把当前帧里的局部名字 s 指向别处，调用者手里那个对象一点没变。要让调用者看见变化，必须是 s.first = ... 这种「顺着引用去改对象内部」的操作。

于是递归有了两个方向：往右走（s.rest，遍历本层）和往下走（s.first，钻进嵌套）。这种「双向递归」是树形结构的标准处理方式，链表在允许嵌套之后其实已经是一棵树了。

代码逐行讲

def deep_map_mut(func, s: Link) -> None:
    if s is Link.empty:
        return
    if isinstance(s.first, Link):
        # A nested linked list: recurse into it instead of calling func.
        deep_map_mut(func, s.first)
    else:
        # A plain value: replace it in place.
        s.first = func(s.first)
    deep_map_mut(func, s.rest)

第 2–3 行：base case。空链表没有任何东西可改，直接 return。注意是光秃秃的 return，不是 return Link.empty——题目要求函数返回 None，而 return 正好返回 None。这个 base case 同时守住了两条递归路径：往右走到尽头会撞上它，往下走时如果子链是空的也会撞上它。

第 4 行：isinstance(s.first, Link) 是题面明确提示的判断方式。为什么不用 type(s.first) == Link？isinstance 对子类也返回 True，语义更宽；而且它是 61A 反复使用的写法。注意判断的是 s.first（元素）而不是 s（当前节点）——s 走到这里必然是 Link，判断它没意义。

第 6 行：往下钻。deep_map_mut(func, s.first) 把子链整个交给自己处理。这一行没有赋值，因为不需要：子链的每个节点会在深层被 s.first = func(s.first) 就地改掉，而 s.first 这个引用始终指着同一个子链对象。写成 s.first = deep_map_mut(func, s.first) 是致命错误——函数返回 None，你会把整个子链替换成 None，后面 print 出来是 (9 None 25 36)，甚至因为 None 不合法而在别处崩掉。

第 9 行：往右走。注意它在 if/else 外面，缩进和 if 齐平——不管当前节点是数还是子链，处理完都要继续走向下一个节点。如果把它缩进到 else 里，那么一旦遇到嵌套元素，后面的所有节点就再也走不到了：link1 会变成 (9 (16) 5 6)，5 和 6 没被平方。

验证：手动追踪 deep_map_mut(square, link1)

link1 是 (3 (4) 5 6)，四个节点记作 N1(3)、N2(子链)、N3(5)、N4(6)，子链里那个节点记作 M1(4)。

① deep_map_mut(square, N1链)
   s = N1，非空
   s.first = 3，不是 Link → else 分支
   s.first = square(3) = 9        ★ N1 被改：3 → 9
   继续 deep_map_mut(square, N2链)

   ② deep_map_mut(square, N2链)
      s = N2，非空
      s.first = Link(4)，是 Link → if 分支
      deep_map_mut(square, M1链)   ← 往下钻

      ③ deep_map_mut(square, M1链)
         s = M1，非空
         s.first = 4，不是 Link → else
         s.first = square(4) = 16   ★ M1 被改：4 → 16
         deep_map_mut(square, M1.rest)

         ④ M1.rest is Link.empty → 立即 return

         ③ 返回 None

      回到 ②：注意这里没有给 N2.first 赋值，
              N2.first 仍指着同一个子链对象，只是它里面的 4 变成了 16
      继续 deep_map_mut(square, N3链)

      ⑤ deep_map_mut(square, N3链)
         s.first = 5，else → s.first = 25    ★ N3：5 → 25
         继续 deep_map_mut(square, N4链)

         ⑥ s.first = 6，else → s.first = 36  ★ N4：6 → 36
            继续 deep_map_mut(square, N4.rest)
            ⑦ 空 → return
         ⑥ 返回
      ⑤ 返回
   ② 返回
① 返回 None

改完之后的内存图：

link1 → [ 9 |•] → [ • |•] → [ 25 |•] → [ 36 |/]
                    ↓
                  [ 16 |/]

节点对象一个都没换，只是每个 first 里的数被覆盖了。
Link.__init__ 从头到尾没被调用过一次，
所以那个假 __init__ 的警告一行都没打印。

print(link1) 走 __str__：第一个节点拼 "9 "，第二个节点的 first 是 Link，str(Link(16)) 递归地得到 "(16)"，拼成 "9 (16) "，再拼 "25 "，最后一个节点走出 while 循环拼上 "36)"。总输出 (9 (16) 25 36)，与 doctest 一致。

link2 同理：double 会钻两层才碰到 2 和 3，得到 (2 ((4 6)) 8)。

与 Q1 对照着记

这张表是链表题的两套模板。以后拿到一道链表题，第一件事就是判断它要的是「新建」还是「就地」，然后套对应的一列。

3. 平方根级素数判定 is_prime_sqrt

题目要什么

判断 n 是不是素数，要求运行时间是 \(\Theta(\sqrt{n})\)。可以假设 n >= 2。题面给的提示只有一句：「你不需要检查每一个比 n 小的数是否整除 n。」

doctest 里的输入值本身就是题目的一部分：

>>> is_prime_sqrt(2)
True
>>> is_prime_sqrt(67092481)
False
>>> is_prime_sqrt(524287)
True
>>> is_prime_sqrt(2251748274470911)
False
>>> is_prime_sqrt(6700417)
True
>>> is_prime_sqrt(44895587973889)
False
>>> is_prime_sqrt(2147483647)
True
>>> is_prime_sqrt(67280421310721)
True

注意 2251748274470911 和 67280421310721 这种量级——两万亿、六十七万亿。这些数字是在替测试用例说话：如果你写的是 \(\Theta(n)\) 的循环，跑到 \(2.25 \times 10^{15}\) 次要几十年。测试通不通过，本质上就是在测你的增长阶对不对。

先把「效率」这件事说清楚

这门课衡量运行时间的方式很朴素：数一数这段代码执行了多少次基本操作，然后看这个次数随输入怎么变。乘法、取模、比较都算一次操作，不管数字多大（题面明确说了：61A 里把这些当常数时间，真实情况留给 61B 和 CS 170）。

本题要求的 \(\Theta(\sqrt{n})\) 不在这张表里——它介于对数和线性之间。别被它吓到：形状上它还是「一重循环」，只是循环上界从 \(n\) 变成了 \(\sqrt{n}\)。

怎么想到的

最朴素的写法是这样，先写出来再改：

def is_prime_slow(n):
    k = 2
    while k < n:
        if n % k == 0:
            return False
        k += 1
    return True

循环最多跑 \(n - 2\) 轮，所以是 \(\Theta(n)\)。对 n = 2147483647（这是个素数，会一直跑到底）要做二十亿次取模，本地大概要跑十几分钟；对 \(6.7 \times 10^{13}\) 那个输入，基本等于永远不结束。

要提速，得先问一个数学问题：一个合数的最小因子最大能有多大？

举个具体的：\(n = 36\)，\(\sqrt{36} = 6\)。它的因子对是 \((2,18), (3,12), (4,9), (6,6)\)。每一对里较小的那个都 \(\le 6\)。因子是成对出现的，以 \(\sqrt{n}\) 为对称轴——查完前半边，后半边不用查了，因为它们的搭档已经被查过。

循环上界从 \(n\) 降到 \(\sqrt{n}\)，操作次数就从 \(\Theta(n)\) 降到 \(\Theta(\sqrt{n})\)。对 \(n = 6.7 \times 10^{13}\)，\(\sqrt{n} \approx 8.2 \times 10^6\)——八百万次，一两秒的事。

第二个观察：跳过偶数

这不影响增长阶（\(\sqrt{n}/2\) 仍然是 \(\Theta(\sqrt{n})\)，系数被忽略），但常数减半，而且写法更利落：只要先单独处理掉 2 的情况，之后所有偶数因子都不用试了——如果 n 是奇数，它不可能被任何偶数整除。所以循环从 3 开始、每次 +2。

第三个观察：不要用 sqrt() 做比较

这是本题最容易踩、也最难 debug 的地方。题面在代码里留了一行注释 # sqrt(k) will give the square root of k as a floating point (decimal)，看着像提示你去用它，其实是一个陷阱预告。

顺带一提：sqrt(n) 如果放在循环条件里，每轮都会重算一次开方，白白浪费时间（虽然不改变增长阶）。divisor * divisor 是一次整数乘法，反而更快。

代码逐行讲

from math import sqrt
def is_prime_sqrt(n: int) -> bool:
    # sqrt(k) will give the square root of k as a floating point (decimal)
    if n % 2 == 0:
        return n == 2
    # Only odd divisors up to sqrt(n) can be the smallest factor of n.
    # Using divisor * divisor <= n avoids float rounding for huge n.
    divisor = 3
    while divisor * divisor <= n:
        if n % divisor == 0:
            return False
        divisor += 2
    return True

第 4–5 行：一行处理掉所有偶数。return n == 2 这个写法把两种情况合并了：n 是偶数时，它是素数当且仅当它就是 2。写成 if n == 2: return True; elif n % 2 == 0: return False 完全等价，只是多两行。这一步是后面「每次 +2」的前提——跳过这步直接从 3 开始步长 2，is_prime_sqrt(4) 会返回 True（因为 \(3 \times 3 = 9 > 4\)，循环一轮都不跑）。

第 8 行：divisor = 3。因为 2 已经被上一步排除干净了。

第 9 行：while divisor * divisor <= n。用 <= 而不是 < 很关键：考虑 n = 9，\(3 \times 3 = 9\)，用 <= 才会进入循环、发现 9 % 3 == 0、返回 False。用 < 的话循环一次都不跑，9 被误判成素数。完全平方数是这道题的经典边界情况，测试里的 67092481 = 8191² 就是专门来抓它的。

第 10–11 行：找到因子立刻返回 False。注意 return 在 while 里面——这里 return 是正确的（找到一个反例就能下结论），和「return 误写在循环里导致只跑一轮」那类 bug 不同。区别在于：这个 return 在 if 的保护下，只有条件成立才触发。

第 12 行：divisor += 2，只试奇数。

第 13 行：循环正常结束意味着 \(2\) 到 \(\lfloor\sqrt{n}\rfloor\) 之间没有任何因子，根据上面的定理，n 是素数。这个 return True 必须在 while 外面——放在里面的话，试完 3 不整除就立刻返回 True，等于只检查了一个因子。

验证一：is_prime_sqrt(2)

一次循环都没进，\(\Theta(1)\) 完事。与 doctest 一致。

验证二：is_prime_sqrt(67092481)（这个数是 \(8191^2\)）

它是完全平方数，最小因子恰好等于 \(\sqrt{n}\)，是最考验边界的一个：

循环走到 divisor = 8191 时，8191 * 8191 == 67092481，正好等于 n。因为条件写的是 <=，这一轮进得去，取模得 0，返回 False。如果条件写成 <，这一轮不进，循环结束返回 True——doctest 立刻失败。整个过程约 4095 轮，瞬间完成。

验证三：is_prime_sqrt(2147483647)（这是个素数，\(2^{31}-1\)）

它是奇数，跳过第一个 if。循环从 3 试到 \(\lfloor\sqrt{2147483647}\rfloor = 46340\)，全部不整除，共约 \((46340-3)/2 \approx 23169\) 轮，然后返回 True。两万三千次取模在现代机器上是毫秒级。

对比一下：\(\Theta(n)\) 的朴素版本在这个输入上要跑 21 亿轮，慢了大约 九万倍。这就是把 \(\Theta(n)\) 换成 \(\Theta(\sqrt{n})\) 的真实收益。

4. 进入 Scheme：动手前必须懂的五件事

后三道题都用 Scheme 写。Scheme 的语法小到可以在一页纸上讲完，但它的求值规则和 Python 是同一套，只是被扒光了糖衣。先把这五件事搞定，再看题就顺了。

一、一切都是调用表达式

Scheme 用前缀记法（Polish prefix notation）：算子写在最前面，后面跟算子数，整体用一对括号包起来。

没有中缀运算符，没有运算符优先级——括号已经把结构写死了，不存在「先乘除后加减」这种规则要记。求值规则和 Python 的调用表达式一字不差：

所以 (* 3 (+ 4 2)) 的过程是：查到 * 是乘法过程 → 求 3 得 3 → 求 (+ 4 2)（这本身又是一个调用表达式，递归走一遍这三步）得 6 → 应用乘法得 18。

二、define 绑定名字

scm> (define pi (+ 3 0.14))
pi
scm> pi
3.14

规则：先求最后那个子表达式的值，再把值绑定到符号上，然后返回符号本身。这就是为什么 REPL 里敲完 define 会回显一个 pi——不是 3.14，是名字。这点和 Python 的赋值语句（不返回任何东西）不同，做 WWSD 题时经常考。

定义过程用同一个 define，只是第一个参数变成一个列表：

(define (square n) (* n n))

读作：定义一个叫 square 的过程，形参是 n，函数体是 (* n n)。对应 Python 的 def square(n): return n * n。没有 return——函数体最后一个表达式的值就是返回值。

三、cond 是 Scheme 的 if/elif/else

(cond (<p1> <e1>)
      (<p2> <e2>)
      ...
      (else <e-else>))

每个子句是一对括号，里面第一个是谓词（predicate），第二个是该谓词为真时要返回的表达式。求值规则：从上到下依次求谓词，遇到第一个为真的就求值并返回它对应的表达式，后面的谓词根本不会被求值（和 Python 的 elif 一样短路）。else 子句可选，全都不成立时走它。

四、还有 if 和 begin

(if <谓词> <真时表达式> <假时表达式>)——注意它是表达式，有返回值，更像 Python 的三元 a if p else b，而不是 if 语句。

(begin <e1> <e2> ... <en>)——按顺序求值一串表达式，返回最后一个的值。它的用处是：if 的每个分支只能放一个表达式，当你需要在一个分支里干好几件事（比如先 define 一个中间变量再算结果），就用 begin 把它们包成一个表达式。Q5 用的正是这个。

五、没有循环，只有递归

Scheme 没有 while、没有 for。所有重复都靠过程调用自己来完成。这不是缺陷，是这门课想让你体会的事：递归足以表达一切迭代，而且往往表达得更清楚。

本仓库的 Scheme 代码全在 hw/hw05/hw05.scm。想手动试，在该目录下运行 python3 scheme -i hw05.scm 进入交互式解释器，(exit) 退出。

5. 快速幂 pow

题目要什么

实现 (pow base exp)，算 base 的 exp 次方，exp 是非负整数。关键约束：递归调用次数要随 exp 对数增长，而不是线性增长。题面举例：(pow 2 32) 应该只递归几次，而不是 32 次。

题面给的两条数学提示就是答案的骨架：

ok 的测试用例是：

scm> (pow 2 5)
32
scm> (pow 10 3)
1000
scm> (pow 3 3)
27
scm> (pow 1 100000000000000) ; make sure this doesn't run forever!
1

最后一个用例是整道题的裁判：指数是 \(10^{14}\)。线性写法要递归一百万亿次，秒挂。对数写法只需要约 \(\log_2 10^{14} \approx 47\) 层。它测的不是正确性，是增长阶。

怎么想到的

朴素写法一眼就能写：

(define (pow base exp)
  (if (= exp 0)
      1
      (* base (pow base (- exp 1)))))

每次指数减 1，递归深度是 exp，即 \(\Theta(\text{exp})\)。对 \(10^{14}\) 完全不可行——而且在 Scheme 解释器里会先撞上递归深度上限报错。

要变成对数，核心问题是：怎么让每一步把问题规模「除以 2」而不是「减 1」？凡是 \(\Theta(\log n)\) 的算法，本质上都在回答这个问题（二分查找、辗转相除、这道题都是）。

指数运算恰好有这个性质：\(x^{8}\) 不需要乘八次，只要算出 \(x^{4}\) 再自乘一次就行；而 \(x^{4}\) 又只要算出 \(x^{2}\) 再自乘。每一步指数折半。

这里有一个容易走的弯路：奇数分支写成 (* base (square (pow base (quotient exp 2))))，直接对应题面给的第二条恒等式 \(x^{2y+1} = x(x^y)^2\)。这样写也对，而且更「快」一点（奇数步也折半了）。但要注意此时必须用整数除法 quotient 而不是 /——奇数除以 2 用 / 会得到分数或小数，指数就错了。本仓库选的是「奇数先减 1」的写法，因为它只在偶数时用 /，永远是整除，不需要额外担心除法语义。

代码逐行讲

(define (square n) (* n n))

; Fast exponentiation: halving exp gives O(log exp) recursive pow calls.
(define (pow base exp)
  (cond ((= exp 0) 1)
        ((even? exp) (square (pow base (/ exp 2))))
        (else (* base (pow base (- exp 1))))))

(define (square n) (* n n))：题面已经给好了，直接用。

((= exp 0) 1)：base case。任何数的 0 次方是 1。这必须是第一个子句——如果放在 even? 后面，exp = 0 会先被判成偶数，递归调用 (pow base 0)，无限循环。cond 子句的顺序就是程序逻辑的一部分。

((even? exp) (square (pow base (/ exp 2))))：偶数分支。(/ exp 2) 因为 exp 是偶数，结果一定是整数。(pow base (/ exp 2)) 先递归算出半个指数的幂，square 再把它平方。注意只递归了一次——如果写成 (* (pow base (/ exp 2)) (pow base (/ exp 2)))，看起来数学上一样，但会产生两次递归调用，整棵调用树的规模从 \(\log n\) 层变成 \(2^{\log n} = n\) 个节点，退化回线性甚至更糟。这是本题最隐蔽的效率陷阱。

(else (* base (pow base (- exp 1))))：奇数分支。掰下一个 base，指数减 1 变成偶数，交给下一层去折半。

验证：手动展开 (pow 2 5)

(pow 2 5)
  exp=5：不为 0；(even? 5) → #f；走 else
  = (* 2 (pow 2 4))
             ↓
  (pow 2 4)
    exp=4：(even? 4) → #t
    = (square (pow 2 2))
                ↓
    (pow 2 2)
      exp=2：(even? 2) → #t
      = (square (pow 2 1))
                  ↓
      (pow 2 1)
        exp=1：(even? 1) → #f；走 else
        = (* 2 (pow 2 0))
                   ↓
        (pow 2 0)
          exp=0 → 返回 1          ← 触底

回代：
  (pow 2 0) = 1
  (pow 2 1) = (* 2 1)      = 2
  (pow 2 2) = (square 2)   = 4
  (pow 2 4) = (square 4)   = 16
  (pow 2 5) = (* 2 16)     = 32   ✓

五层递归得到 32，与测试用例一致。

验证：(pow 1 100000000000000) 为什么不会跑死

指数 \(10^{14}\) 是偶数，第一步就折半成 \(5 \times 10^{13}\)；这是奇数，减 1 变偶数再折半……大致规律是：每遇到一个偶数指数就折半，遇到奇数先减 1（下一步必折半）。所以最多 \(2\log_2(10^{14}) \approx 2 \times 46.5 \approx 93\) 层递归就能到底。

作为对比，朴素写法要 \(10^{14}\) 层。这个测试用例的注释 ; make sure this doesn't run forever! 就是在明说这一点。

6. 反复立方 repeatedly-cube

题目要什么

实现 (repeatedly-cube n x)：把 x 立方 n 次。注意参数顺序——n 在前，x 在后，而题目描述里写的是「receives a number x and cubes it n times」，读的顺序和参数顺序是反的，很容易写反。

scm> (repeatedly-cube 100 1) ; 1 cubed 100 times is still 1
1
scm> (repeatedly-cube 2 2)   ; (2^3)^3
512
scm> (repeatedly-cube 3 2)   ; ((2^3)^3)^3
134217728

验算一下第三个：\(2^3 = 8\)，\(8^3 = 512\)，\(512^3 = 134217728\)。确实是「立方三次」，不是「三次方」。

更重要的是，题面给了一个带空格的骨架，这不是建议，是在指定解法形状：

(define (repeatedly-cube n x)
    (if (zero? n)
        x
        (begin
            (define y ___)
            ___)))

骨架里出现了 begin 和一个函数体内的 define。这道题的真正目的不是算立方，而是让你用一次 begin 和一次局部 define。

怎么想到的：先问骨架为什么长这样

如果不看骨架，最直接的写法是：

(define (repeatedly-cube n x)
  (if (zero? n)
      x
      (cube (repeatedly-cube (- n 1) x))))

但 Scheme 里没有内置的 cube，你得写成 (* r r r)，其中 r 是递归结果。于是问题来了：

(* (repeatedly-cube (- n 1) x)
   (repeatedly-cube (- n 1) x)
   (repeatedly-cube (- n 1) x))

这就递归了三次，而三次里算的是完全一样的东西。和 Q4 里那个陷阱一模一样：调用树每层分叉三倍，深度 n，总共 \(\Theta(3^n)\) 次调用。(repeatedly-cube 3 2) 还能撑住（27 次），(repeatedly-cube 100 1) 就是 \(3^{100}\)，宇宙热寂都算不完。

而 begin 的必要性也就清楚了：if 的假分支只能放一个表达式，但我们要做两件事（先 define，再计算）。begin 把这两件事打包成一个表达式，返回最后一个的值。

代码逐行讲

(define (repeatedly-cube n x)
  (if (zero? n)
      x
      (begin
        ; Cube x n-1 times first, name that result y, then cube it once more.
        (define y (repeatedly-cube (- n 1) x))
        (* y y y))))

(if (zero? n) x ...)：base case。立方 0 次就是 x 本身，原样返回。(zero? n) 等价于 (= n 0)，题面骨架用的就是 zero?。

(begin ...)：把两个表达式串成一个。begin 返回最后一个表达式的值，也就是 (* y y y)。(define y ...) 的返回值（符号 y）被丢弃，这里只要它的副作用——建立绑定。

(define y (repeatedly-cube (- n 1) x))：先把「立方 n-1 次」的结果算出来。注意参数顺序是 (- n 1) 在前、x 在后，和函数签名一致。x 一路原封不动往下传，只有 n 在减少。

(* y y y)：把这个结果再立方一次。y 只是一个名字查找，不会重新触发递归。整个函数只有一次递归调用，这是本题的全部意义所在。

验证：手动展开 (repeatedly-cube 3 2)

(repeatedly-cube 3 2)
  n=3，(zero? 3) → #f，进入 begin
  需要 y = (repeatedly-cube 2 2)
             ↓
  (repeatedly-cube 2 2)
    n=2，非零，进入 begin
    需要 y = (repeatedly-cube 1 2)
               ↓
    (repeatedly-cube 1 2)
      n=1，非零，进入 begin
      需要 y = (repeatedly-cube 0 2)
                 ↓
      (repeatedly-cube 0 2)
        n=0，(zero? 0) → #t，返回 x = 2   ← 触底

回代（每层各有一个自己的 y）：
  第 3 层（n=1）：y = 2
                 (* 2 2 2) = 8
  第 2 层（n=2）：y = 8
                 (* 8 8 8) = 512
  第 1 层（n=3）：y = 512
                 (* 512 512 512) = 134217728   ✓

三层递归，每层一次乘法（三元乘法），得到 134217728，与测试用例一致。

每层的帧长什么样

全局环境
  repeatedly-cube → 过程对象

f1: repeatedly-cube  [parent = 全局]
    n = 3, x = 2
    y = 512                （回代时才绑定）
    正在算 (* y y y)

  f2: repeatedly-cube  [parent = 全局]
      n = 2, x = 2
      y = 8

    f3: repeatedly-cube  [parent = 全局]
        n = 1, x = 2
        y = 2

      f4: repeatedly-cube  [parent = 全局]
          n = 0, x = 2
          （直接返回 x，没有 y）

注意每一帧的 parent 都是全局环境，不是调用者的帧——
Scheme 和 Python 一样是词法作用域（lexical scope），
帧的 parent 由过程「定义在哪」决定，而不是「被谁调用」。
所以四个 y 完全隔离，f1 的 y 和 f3 的 y 互不影响。

再看 (repeatedly-cube 100 1)：100 层递归，每层 y 都是 1（因为 \(1^3 = 1\)），最后返回 1。100 层对解释器是小意思。而三次递归的错误版本在这里要做 \(3^{100} \approx 5 \times 10^{47}\) 次调用，直接卡死。

7. 取第二、第三个元素 cadr 与 caddr

题目要什么

定义 cadr（返回列表的第二个元素）和 caddr（返回第三个元素），要求用 car 和 cdr 组合出来。题面已经给好了 cddr：

(define (cddr s)
  (cdr (cdr s)))

测试用例：

scm> (cddr '(1 2 3 4))
(3 4)
scm> (cadr '(1 2 3 4))
2
scm> (caddr '(1 2 3 4))
3

先搞懂 Scheme 列表到底是什么

这道题代码只有两行，但如果不理解列表的内部结构，这两行就是死记硬背。

Scheme 的列表和 Python 的 Link 是同一个东西，只是叫法不同。一个 pair 有两个格子，car 取第一个，cdr 取第二个。列表 (1 2 3 4) 实际上是四个 pair 串起来：

'(1 2 3 4)

  [ 1 | •] → [ 2 | •] → [ 3 | •] → [ 4 | () ]
    ↑    ↑
   car  cdr

(car '(1 2 3 4))  =  1          ← 第一个格子里的值
(cdr '(1 2 3 4))  =  (2 3 4)    ← 第二个格子里的指针，指向剩下的表

怎么想到的

先破解命名规律。cadr 这个名字读起来像乱码，但它是有结构的：c + 一串 a/d + r。中间每个字母代表一次操作，a 是 car，d 是 cdr，而且从右往左依次执行。

「从右往左」不是硬记的规则，它就是括号嵌套的求值顺序：(car (cdr s)) 里最里面的 cdr 先算，写成名字时 d 就靠右。名字的字母顺序和代码里从外到内的顺序一致。

代码逐行讲

(define (cddr s) (cdr (cdr s)))

(define (cadr s) (car (cdr s)))

(define (caddr s) (car (cddr s)))

(cadr s) = (car (cdr s))：内层 (cdr s) 先求值，把 (1 2 3 4) 变成 (2 3 4)；外层 car 取出 2。

(caddr s) = (car (cddr s))：复用已经定义好的 cddr。当然也可以写成 (car (cdr (cdr s)))，完全等价，ok 都能过。用 cddr 更好，理由是抽象复用：cddr 这个名字已经表达了「跳过两个」这个概念，读代码的人不用再数括号。这门课反复强调的「用名字给中间概念命名」，在这两行里体现得最简洁。

验证：(caddr '(1 2 3 4))

(caddr '(1 2 3 4))

第 1 步：应用 caddr，形参 s 绑定到 (1 2 3 4)
        函数体是 (car (cddr s))

第 2 步：求算子数 (cddr s)
        应用 cddr，函数体是 (cdr (cdr s))

        第 2a 步：内层 (cdr s)
                  [1|•]→[2|•]→[3|•]→[4|()]
                  跳过第一个格子，得到 (2 3 4)

        第 2b 步：外层 (cdr (2 3 4))
                  跳过第一个格子，得到 (3 4)

        cddr 返回 (3 4)

第 3 步：外层 (car (3 4))
        取第一个格子里的值 → 3

返回 3   ✓

同理 (cadr '(1 2 3 4))：(cdr s) 得 (2 3 4)，car 取出 2。(cddr '(1 2 3 4)) 得 (3 4)——注意它返回的是一个列表，所以 REPL 显示带括号的 (3 4)，而 cadr/caddr 返回的是元素本身，显示成裸的数字。这个区别就是 car 和 cdr 的区别。

整份作业回顾

六道题，三个主题，但真正学到的是三种可迁移的思考方式。

一、递归数据结构决定递归代码

链表的定义是「空 或 值+链表」，所以处理它的函数天然长成「if 空 → base case；否则 → 处理 first + 递归处理 rest」。Q1 和 Q2 是这个模板的两个变体：造新的（返回 Link(...)）和改旧的（赋值 .first）。Q2 多了一层「元素本身也可能是链表」，于是递归从一维变成两维——往右和往下。Scheme 的列表（Q6）是同一个结构换了身衣服，car/cdr 就是 first/rest。看穿这一点，Q6 就不需要背了。

二、把「重复计算」找出来，是所有提速的第一步

Q3、Q4、Q5 表面上是三道无关的题，其实都在问同一个问题：你做的功里有多少是白费的？

共同的手法是：给中间结果起个名字，只算一次。在 Scheme 里就是 define，在 Python 里就是赋值，在 pow 里是套一个 square。这个动作在代码上只多一行，在运行时间上是几个数量级。

另一个反复出现的手法是每步把问题除以常数而不是减去常数。\(\Theta(\log n)\) 算法的特征就是这个。看到「不许线性」的要求，第一反应应该是「能不能折半」。

三、就地修改与新建，是两种不同的世界观

Q2 的 Construct Check（那段替换 Link.__init__ 的黑魔法）不是刁难，它在强制你区分两件事：

• 新建：函数是纯的，输入不变，返回新东西。好处是安全、可组合；代价是内存和拷贝成本。
• 就地修改：函数返回 None，效果发生在参数对象上。好处是省内存、能改共享结构；代价是所有持有该对象引用的地方都被牵连——别名（aliasing）问题从此开始。

Q1 里那个「直接把 l2 接到 l1 尾巴上」的诱人写法之所以会造成死循环，根源就是没意识到自己在做就地修改。写每一行链表代码之前，先明确这一行是在读还是在写。

四、Scheme 不是新语言，是同一套求值规则的裸露版

Scheme 只有调用表达式和几个特殊形式（define、if、cond、begin、quote）。特殊形式之所以特殊，就是因为它们不按标准的「先求所有子表达式再 apply」的规则来——if 只求一个分支，cond 短路，define 不求第一个参数，quote 什么都不求。把这个清单记住，剩下的一切都是普通的调用表达式。

本次得分

本仓库 hw/hw05/ 目录下运行 python3 ok --local，11 个测试用例全部通过，六道题无一失分。Q1–Q3 是 Python doctest（含 Q2 的 Construct Check），Q4–Q6 由 tests/pow.py、tests/repeatedly-cube.py、tests/cadr-caddr.py 三个 Scheme 测试套件驱动，每套先执行 (load-all ".") 加载 hw05.scm，再逐条比对 REPL 输出。