HW 2：递归、树递归、序列与列表ok 6 项通过

0. 这份作业在练什么

HW 2 一共六道必做题（Q1–Q6），外加一道选做的 Q7。本仓库里 python3 ok --local 的结果是 6 个测试用例全部通过，也就是说下面贴出来的每一段代码都真的跑通过官方评分器，不是我凭印象敲的。 （Q7 是 optional，评分器不计入这 6 项，但我也一并做了并在文末讲。）

这份作业的主线只有一句话：把一个问题，表达成「同一个问题的更小版本」加上「一点点收尾工作」。 这句话听上去像废话，真正难的是三件具体的事：

1. 选什么当「更小」。对整数来说，「更小」通常是 num // 10（砍掉最后一位）； 对列表来说，「更小」是去掉第一个元素、或者是「某个更内层的子列表」；对找零钱来说，「更小」有两个维度 ——剩余金额变小，或者可用面额变少。选错了维度，递归就永远停不下来。
2. base case 到底停在哪。停早了会漏算，停晚了会算重，停错了会无限递归直接 RecursionError: maximum recursion depth exceeded。
3. 递归调用返回来的那个值，语义是什么。这是最关键的一点：你必须在写 return 之前， 先用一句话说清楚「f(更小的输入) 给我的是什么」，然后才知道该怎么把它拼成答案。 CS 61A 管这个叫 recursive leap of faith（递归的信心之跃）——假设更小的那次调用已经对了， 你只需要写对「从小到大」这一步。

做之前该会什么

>>> from construct_check import check
>>> check(SOURCE_FILE, 'num_eights',
...       ['Assign', 'AnnAssign', 'AugAssign', 'NamedExpr', 'For', 'While'])
True

1. Num Eights：数一个整数里有几个 8

题目要什么

写一个递归函数 num_eights(num)，输入是一个正整数，返回数字 8 在它的十进制表示里出现了几次。

>>> num_eights(3)
0
>>> num_eights(8)
1
>>> num_eights(88888888)
8
>>> num_eights(2638)
1
>>> num_eights(86380)
2
>>> num_eights(12345)
0
>>> num_eights(8782089)
3

翻译成人话：把 num 当成一串数字符号看，数里面有几个 8。 num_eights(86380) 是 2，因为 8、6、3、8、0 里有两个 8——注意末尾的 0 一点也不特殊， 它只是「不是 8」而已。

边界情况有两个值得先想清楚：

• 一位数：num_eights(3) 要返回 0，num_eights(8) 要返回 1。 这是递归的终点，必须单独处理。
• 末位是 0：86380 // 10 == 8638，去掉末位不会有任何麻烦。 但如果你写的是「把数转成字符串再数」——题目允许吗？允许，但那样就不是在练递归了， 而且这题的 check 禁了赋值语句，字符串解法通常也写不下去。

怎么想到的

第一步，先别管递归，问自己：如果允许用循环，我会怎么写？

total = 0
while num > 0:
    if num % 10 == 8:
        total = total + 1
    num = num // 10
return total

这个版本谁都会写：每轮看一眼末位是不是 8，是就计数加一，然后把末位砍掉，直到数被砍空。 它揭示了两个关键操作：num % 10 拿到末位，num // 10 得到「去掉末位后的那个数」。

第二步，把循环翻译成递归。翻译的秘诀是问：「去掉末位后剩下的那个数」里有几个 8，谁来数？ 答案是——让 num_eights 自己去数。这就是信心之跃：我假设 num_eights(263) 已经能正确返回 0，那么 num_eights(2638) 就等于 「263 里的 8 的个数」加上「末位 8 是不是 8」= 0 + 1 = 1。

第三步，定 base case。递归每次把 num 缩小 10 倍，迟早会变成一位数。 一位数的时候不能再砍了（8 // 10 == 0，再往下就是 num_eights(0)， 虽然也能靠 num == 0 收住，但题目说输入是正整数，用 0 当 base case 语义上有点绕）。 所以我选 num < 10：这时候整个数就是一位，它是 8 就返回 1，否则返回 0。

这里我走过一条弯路，值得写下来。我最初写的 base case 是：

if num == 0:
    return 0

然后主体统一写 return (1 if num % 10 == 8 else 0) + num_eights(num // 10)。 这版其实也是对的，逻辑上更整齐。但它有个隐患：num_eights(0) 会返回 0， 而如果有人真的传了 0 进来（题目保证不会，但你的心里模型要清楚）， 「0 这个数里有几个 8」的答案是 0——恰好蒙对。可换成 num_eights(80) 走这条路： 80 → 8 → 0，三层，末层返回 0，中间层看到 8 % 10 == 8 补 1，结果是 1。正确。 两版都能过。我最终选了 num < 10 那版，因为它在一位数就停， 递归深度少一层，而且「一位数是不是 8」这句话读起来就是人话。

代码

def num_eights(num: int) -> int:
    # The last digit contributes 1 if it is an 8, and we recurse on the rest.
    if num < 10:
        return 1 if num == 8 else 0
    elif num % 10 == 8:
        return 1 + num_eights(num // 10)
    else:
        return num_eights(num // 10)

逐行讲：

验证：手动追踪 num_eights(8782089)

doctest 说它应该返回 3（8、8、8 三个八：8782089 的数字依次是 8,7,8,2,0,8,9）。 把调用栈真的展开——注意递归是从末位往前处理的：

num_eights(8782089)
  8782089 >= 10, 8782089 % 10 == 9 != 8  → 走 else
  = num_eights(878208)
      878208 % 10 == 8  → 走 elif
      = 1 + num_eights(87820)
            87820 % 10 == 0 != 8 → else
            = num_eights(8782)
                  8782 % 10 == 2 != 8 → else
                  = num_eights(878)
                        878 % 10 == 8 → elif
                        = 1 + num_eights(87)
                              87 % 10 == 7 != 8 → else
                              = num_eights(8)
                                    8 < 10  → base case
                                    = 1

num_eights(8)       = 1
num_eights(87)      = num_eights(8)        = 1
num_eights(878)     = 1 + num_eights(87)   = 1 + 1 = 2
num_eights(8782)    = num_eights(878)      = 2
num_eights(87820)   = num_eights(8782)     = 2
num_eights(878208)  = 1 + num_eights(87820) = 1 + 2 = 3
num_eights(8782089) = num_eights(878208)   = 3   ✓

七层调用，其中三层执行了 1 +，正好对应三个 8。用表格再看一遍每一层在干什么：

再快速验一个：num_eights(12345)。12345 → 1234 → 123 → 12 → 1， 每一位都不是 8，五层全走 else，最底层 1 < 10 且 1 != 8 返回 0， 一路原样传回来，结果 0。✓

2. Digit Distance：相邻数位之差的绝对值之和

题目要什么

一个整数的 digit distance 定义为：把它的十进制数位排成一排， 把每一对相邻数位的差取绝对值，再全部加起来。

• 61 的 digit distance 是 5，因为 abs(6 - 1) == 5。
• 71253 是 12，因为 abs(7-1) + abs(1-2) + abs(2-5) + abs(5-3) = 6 + 1 + 3 + 2 = 12。
• 6 是 0，因为一位数根本没有相邻数位对。

>>> digit_distance(3)
0
>>> digit_distance(777) # 0 + 0
0
>>> digit_distance(314) # 2 + 3
5
>>> digit_distance(31415926535) # 2 + 3 + 3 + 4 + ... + 2
32
>>> digit_distance(3464660003)  # 1 + 2 + 2 + 2 + ... + 3
16

禁令是 ['For', 'While']——这次允许赋值，只是不许循环。 比 Q1 宽松，正好可以用局部名字把代码写清楚。

要点住的边界情况：

• 一位数返回 0。注意「0 对相邻数位」和「相邻数位差都是 0」是两回事， 但结果都是 0，所以 base case 写 return 0 天然正确。
• n 位数有 n-1 对。314 有 3 位、2 对（3-1 和 1-4）。 如果你算出 3 对，说明多算了一对，多半是 base case 停晚了。
• 必须取绝对值。314 的第二对是 abs(1-4) == 3 而不是 -3。 少了 abs，digit_distance(314) 会得到 2 + (-3) = -1。

怎么想到的

Q1 建立的直觉是「砍末位、递归、补一点」。这题的第一个坑就在这个「补一点」上： Q1 里每一位独立贡献，这题的贡献属于「一对」，不属于任何单独一位。 所以第一个问题必须是：递归的每一层，负责的是哪一对？

我最开始的错误想法是：既然要比较相邻两位，那就一次砍掉两位吧—— digit_distance(num // 100)。写出来立刻发现不对： 314 砍两位变成 3，可 3 和 1 那一对我算了， 1 和 4 那一对呢？它跨在被我砍掉的两位里。更根本的问题是： 相邻对是「重叠」的——3-1 和 1-4 共用了中间那个 1。 一次砍两位会把共用的那一位弄丢，所以只能一次砍一位。

怎么拿到倒数第二位？末位是 num % 10。 倒数第二位 = 「去掉末位之后的那个数」的末位 = (num // 10) % 10。 拿 314 验一下：314 % 10 == 4，(314 // 10) % 10 == 31 % 10 == 1。对。

base case 呢？递归每次少一位，什么时候该停？ 当只剩一位时，没有「倒数第二位」可配对了，贡献为 0，直接返回 0。 这就是 if num < 10: return 0。

顺带验证一下配对数量对不对：314 三位 → 第一层算一对（4 与 1）， 递归到 31 两位 → 算一对（1 与 3），递归到 3 一位 → base case 返回 0。 一共 2 对 = 3 - 1。✓

代码

def digit_distance(num: int) -> int:
    # A single digit has no pair of consecutive digits, so distance is 0.
    if num < 10:
        return 0
    last_digit = num % 10
    second_to_last_digit = (num // 10) % 10
    return abs(last_digit - second_to_last_digit) + digit_distance(num // 10)

验证：手动追踪 digit_distance(3464660003)

doctest 说结果是 16。这个数的数位是 3,4,6,4,6,6,0,0,0,3，一共 10 位、9 对。 先按定义横着算一遍：

现在看递归是怎么把这 9 项凑出来的。注意递归是从右往左处理的， 所以它先算出的是最后那一对 0,3：

digit_distance(3464660003)
  末位 3, 次末位 0 → abs(3-0)=3
  = 3 + digit_distance(346466000)
        末位 0, 次末位 0 → abs(0-0)=0
        = 0 + digit_distance(34646600)
              末位 0, 次末位 0 → 0
              = 0 + digit_distance(3464660)
                    末位 0, 次末位 6 → abs(0-6)=6
                    = 6 + digit_distance(346466)
                          末位 6, 次末位 6 → 0
                          = 0 + digit_distance(34646)
                                末位 6, 次末位 4 → 2
                                = 2 + digit_distance(3464)
                                      末位 4, 次末位 6 → 2
                                      = 2 + digit_distance(346)
                                            末位 6, 次末位 4 → 2
                                            = 2 + digit_distance(34)
                                                  末位 4, 次末位 3 → 1
                                                  = 1 + digit_distance(3)
                                                        3 < 10 → 0

digit_distance(3)          = 0
digit_distance(34)         = 1 + 0  = 1
digit_distance(346)        = 2 + 1  = 3
digit_distance(3464)       = 2 + 3  = 5
digit_distance(34646)      = 2 + 5  = 7
digit_distance(346466)     = 0 + 7  = 7
digit_distance(3464660)    = 6 + 7  = 13
digit_distance(34646600)   = 0 + 13 = 13
digit_distance(346466000)  = 0 + 13 = 13
digit_distance(3464660003) = 3 + 13 = 16   ✓

递归产生的贡献序列是 3, 0, 0, 6, 0, 2, 2, 2, 1， 正是横着算那一行 1, 2, 2, 2, 0, 6, 0, 0, 3 倒过来。 这不是巧合：递归从末位往前走，自然是逆序遍历所有相邻对。加法可交换，所以总和一样。

再验一个短的：digit_distance(777)。 末位 7、次末位 7 → 0，加 digit_distance(77)； 77 的末位 7、次末位 7 → 0，加 digit_distance(7)； 7 是一位数 → 0。总和 0 + 0 + 0 = 0。✓ 这个例子还顺便说明：贡献为 0 不等于该停， 停的条件只看位数，不看数值。

3. Interleaved Sum：奇偶交错求和

题目要什么

interleaved_sum(num, f_odd, f_even) 接收一个整数 num 和两个单参数函数， 返回把 f_odd 作用在 1 到 num 之间所有奇数上、 把 f_even 作用在所有偶数上，然后全部加起来的结果。num 本身包含在内。

>>> identity = lambda x: x
>>> square = lambda x: x * x
>>> triple = lambda x: x * 3
>>> interleaved_sum(5, identity, square) # 1   + 2*2 + 3   + 4*4 + 5
29
>>> interleaved_sum(5, square, identity) # 1*1 + 2   + 3*3 + 4   + 5*5
41
>>> interleaved_sum(4, triple, square)   # 1*3 + 2*2 + 3*3 + 4*4
32
>>> interleaved_sum(4, square, triple)   # 1*1 + 2*3 + 3*3 + 4*3
28

禁令有两条：

>>> check(SOURCE_FILE, 'interleaved_sum', ['While', 'For', 'Mod']) # ban loops and %
True
>>> check(SOURCE_FILE, 'interleaved_sum', ['BitAnd', 'BitOr', 'BitXor'])
True

这才是本题真正的难点。不许循环好说，关键是不许用 %—— 也就是说你不能写 if k % 2 == 0 来判断奇偶。位运算 k & 1 也被堵死了。 题面里那句提示说得很明白：

Instead of directly checking whether a number is even or odd, start with 1, which you know is an odd number.

边界情况：

• num 是奇数时（如 5），最后一项 5 要用 f_odd。
• num 是偶数时（如 4），最后一项 4 要用 f_even， 而且不能多加一个 5。
• 如果 num 小于 1（题目没给这种测试，但你的 base case 应该经得起推敲）， 和应该是 0。

怎么想到的

先把「如果能用 %」的版本写出来，看清楚我们到底损失了什么：

# 假想版本，本题不允许这么写
def interleaved_sum(num, f_odd, f_even):
    total, k = 0, 1
    while k <= num:
        if k % 2 == 1:
            total = total + f_odd(k)
        else:
            total = total + f_even(k)
        k = k + 1
    return total

这个版本的核心是：每走一步，都要重新问一遍「我现在这个 k 是奇是偶」。 禁掉 % 之后，这个「问一遍」的能力没了。那怎么办？

用 num = 5 走一遍这个打包：(1,2)、(3,4)、然后 5 落单。 用 num = 4：(1,2)、(3,4)，正好配完。 这就出现了两种收尾情况，正好对应两个 base case。

第二个问题：递归函数需要携带哪些信息？ 显然需要当前的 k。但 interleaved_sum 的签名是固定的三个参数， 没有 k 的位置。我一开始想改成 interleaved_sum(k, num, f_odd, f_even)， 但那会改掉函数签名，doctest 直接调用 interleaved_sum(5, identity, square) 就会崩。

解决办法就是题面的第二条提示：定义一个内层辅助函数。 内层函数 sum_from(k) 只带一个参数 k， 而 num、f_odd、f_even 通过词法作用域直接从外层帧读到—— 这正是 Lecture 4 讲的：内层函数的 parent 是它被定义时所在的那一帧。 不必把它们一路当参数传下去，代码干净得多。

情况 A: k > num
    区间是空的，没有任何项要加  → return 0

情况 B: k == num
    k 是最后一项，而且我们知道 k 是奇数 → return f_odd(k)
    （不能再加 f_even(k+1)，因为 k+1 已经超过 num 了）

情况 C: k < num
    k 是奇数，在范围内            → 加 f_odd(k)
    k+1 <= num，且是偶数          → 加 f_even(k+1)
    剩下从 k+2 开始，k+2 仍是奇数  → 加 sum_from(k+2)
    → return f_odd(k) + f_even(k + 1) + sum_from(k + 2)

情况 C 里那个 k + 1 <= num 的推理值得停一下：既然 k < num 且两者都是整数， 那么 k + 1 <= num 必然成立，所以 f_even(k+1) 这一项一定在范围内， 不需要额外判断。这是 A、B、C 三分而不是两分的全部理由： 如果只写 if k > num: return 0 一个 base case， 那么当 k == num（num 为奇数）时会走进 C， 多加一个 f_even(num + 1)——超界了。 拿 interleaved_sum(5, identity, square) 试： 会变成 1 + 4 + 3 + 16 + 5 + 36 = 65，而不是 29。

代码

def interleaved_sum(num: int, f_odd, f_even) -> int:
    def sum_from(k):
        """Interleaved sum from the odd number k up to num."""
        if k > num:
            return 0
        elif k == num:
            # k is the last term, and we know it is odd.
            return f_odd(k)
        else:
            # k is odd, so k + 1 is even; then jump to the next odd number.
            return f_odd(k) + f_even(k + 1) + sum_from(k + 2)

    return sum_from(1)

验证：手动追踪两个例子

例一：interleaved_sum(5, identity, square)，期望 29。 这里 f_odd = identity（原样返回），f_even = square（平方）。 注意 num = 5 是奇数，会走到 k == num 那条。

sum_from(1)
  1 < 5 → 分支 C
  = identity(1) + square(2) + sum_from(3)
  = 1          + 4         + sum_from(3)

      sum_from(3)
        3 < 5 → 分支 C
        = identity(3) + square(4) + sum_from(5)
        = 3          + 16        + sum_from(5)

            sum_from(5)
              5 == num → 分支 B
              = identity(5) = 5

回代：
sum_from(5) = 5
sum_from(3) = 3 + 16 + 5  = 24
sum_from(1) = 1 + 4  + 24 = 29   ✓

对照注释里的 1 + 2*2 + 3 + 4*4 + 5 = 1 + 4 + 3 + 16 + 5 = 29。 项数、项的归属完全对上。

例二：interleaved_sum(4, triple, square)，期望 32。 f_odd = triple（乘 3），f_even = square。 num = 4 是偶数，会走到 k > num 那条。

sum_from(1)
  1 < 4 → 分支 C
  = triple(1) + square(2) + sum_from(3)
  = 3        + 4         + sum_from(3)

      sum_from(3)
        3 < 4 → 分支 C
        = triple(3) + square(4) + sum_from(5)
        = 9        + 16        + sum_from(5)

            sum_from(5)
              5 > 4 → 分支 A
              = 0

回代：
sum_from(5) = 0
sum_from(3) = 9 + 16 + 0  = 25
sum_from(1) = 3 + 4  + 25 = 32   ✓

对照注释 1*3 + 2*2 + 3*3 + 4*4 = 3 + 4 + 9 + 16 = 32。✓

环境图：内层函数怎么读到 num

这是本题最值得画的东西。调用 interleaved_sum(4, triple, square) 时：

Global 帧
    interleaved_sum  ──→ func interleaved_sum(num, f_odd, f_even) [parent=Global]
    triple           ──→ func λ(x) [parent=Global]
    square           ──→ func λ(x) [parent=Global]

f1: interleaved_sum   [parent=Global]
    num     4
    f_odd   ──→ triple 那个 λ
    f_even  ──→ square 那个 λ
    sum_from ──→ func sum_from(k) [parent=f1]     ← 注意 parent 是 f1，不是 Global
    return value  32

f2: sum_from   [parent=f1]        ← 每次递归调用都新建一帧，parent 都是 f1
    k  1
    正在算: f_odd(1) + f_even(2) + sum_from(3)
    查 f_odd  → f2 里没有 → 去 parent f1 → 找到 triple ✓
    查 num    → f2 里没有 → 去 parent f1 → 找到 4      ✓
    return value  32

f3: sum_from   [parent=f1]
    k  3
    return value  25

f4: sum_from   [parent=f1]
    k  5
    5 > num(4) → return 0

4. Count Dollars：有多少种凑钱的方法

题目要什么

美元纸币面额是 1、5、10、20、50、100。给定正整数 sum_needed， 问：有多少种不同的纸币组合，面值之和恰好等于 sum_needed？ 纸币数量不限，同一面额可以用任意多张。

题面给了 15 的全部 6 种：

>>> count_dollars(15)
6
>>> count_dollars(10)
4
>>> count_dollars(20)
10
>>> count_dollars(45)
44
>>> count_dollars(100)
344
>>> count_dollars(200)
3274

最重要的一句话在这张表里：这是「组合」不是「排列」。 「1 张 $5 + 1 张 $10」和「1 张 $10 + 1 张 $5」算同一种，只数一次。 你的算法必须内建这个「不重复计数」的机制，否则 count_dollars(15) 会得到远大于 6 的数。

题目还要求必须用 next_smaller_dollar：

def next_smaller_dollar(bill: int) -> int:
    """Returns the next smaller bill in order."""
    if bill == 100:
        return 50
    if bill == 50:
        return 20
    if bill == 20:
        return 10
    elif bill == 10:
        return 5
    elif bill == 5:
        return 1

注意最后：next_smaller_dollar(1) 什么都不返回—— 所有 if 都不成立，函数走到末尾，Python 自动返回 None。 这个 None 不是 bug，它是「没有更小的面额了」的信号， 你的 base case 必须接住它。

怎么想到的

先说为什么「直接递归」在这题会失败。最朴素的想法是： 「凑 15 的方法数 = 用一张 $1 之后凑 14 的方法数 + 用一张 $5 之后凑 10 的方法数 + 用一张 $10 之后凑 5 的方法数 + …」 写出来是这样：

# 错误示范
def count_dollars(sum_needed):
    if sum_needed == 0:
        return 1
    if sum_needed < 0:
        return 0
    return (count_dollars(sum_needed - 1) + count_dollars(sum_needed - 5)
            + count_dollars(sum_needed - 10) + ...)

这个版本数的是排列：凑 6 元时，「先 $1 再 $5」和「先 $5 再 $1」被算成两条不同的路径。 count_dollars(15) 会返回一个大得离谱的数。问题的根源是： 这个递归没有记住「我已经决定不再用某些面额了」，导致同一个组合被以不同顺序数了很多遍。

但这里立刻出现一个技术问题：递归需要携带两个信息——还差多少钱，以及当前允许的最大面额。 可 count_dollars 的签名只有一个参数。这就是题面提示说的 「If you need to keep track of more than one value across recursive calls, consider writing a helper function」。 和 Q3 一样，写内层辅助函数：

remaining == 0
    → 一分不差，当前这套组合成立了。这本身就是「一种方法」  → return 1

remaining < 0
    → 上一步用的那张纸币太大，超支了。这条路走不通       → return 0

largest_bill is None
    → 已经把 1 元也排除掉了，没有面额可用；而 remaining 还 > 0
      （因为 remaining == 0 已经先被拦下了）              → return 0

with_bill    = count_using(remaining - largest_bill, largest_bill)
               # 再用一张 largest_bill，上限不降
without_bill = count_using(remaining, next_smaller_dollar(largest_bill))
               # 这档不再用了，换下一档
return with_bill + without_bill

这里有个我一开始搞错的细节：remaining == 0 必须排在 remaining < 0 前面吗？ 其实这两个条件互斥，顺序无所谓。但 remaining == 0 必须排在 largest_bill is None 前面——这一条至关重要。 考虑「用 15 张 $1 凑 15」这条路：最后一次 count_using(0, 1)， remaining 是 0 但 largest_bill 还是 1，没问题。 可如果顺序反了，某些路径会在还剩 0 元、面额已耗尽时被判成 0，漏算。 更直接的理由是：remaining == 0 是成功，不管还有没有面额可用，都该算一种。

最后一个决定：从哪个面额起步？count_using(sum_needed, 100)。 从最大的 100 开始，逐级往下。如果从 1 起步会怎样？ next_smaller_dollar(1) 是 None，第一步就把面额用光了， 只能得到「全用 1 元」这一种（或者 0 种）。方向必须和 next_smaller_dollar 一致。 （选做的 Q7 正是把方向反过来，用 next_larger_dollar，见第 7 节。）

代码

def count_dollars(sum_needed: int) -> int:
    def count_using(remaining, largest_bill):
        """Ways to make `remaining` using bills no larger than largest_bill."""
        if remaining == 0:
            return 1  # Found one complete way to make change.
        elif remaining < 0 or largest_bill is None:
            return 0  # Overshot, or ran out of bill values to try.
        # Either use one more `largest_bill`, or stop using it entirely.
        with_bill = count_using(remaining - largest_bill, largest_bill)
        without_bill = count_using(remaining, next_smaller_dollar(largest_bill))
        return with_bill + without_bill

    return count_using(sum_needed, 100)

验证：把 count_dollars(10) 的整棵树画出来

doctest 说是 4。10 元的四种凑法是：10 张 $1、5 张 $1 + 1 张 $5、2 张 $5、1 张 $10。 我们来看递归树怎么正好数出这 4 片叶子。

入口是 count_using(10, 100)。前面几层没有悬念： 100 和 50 都比 10 大，用一张就超支；20 也一样。所以：

count_using(10, 100)
  with_bill    = count_using(-90, 100)  → remaining < 0 → 0
  without_bill = count_using(10, 50)
  = 0 + count_using(10, 50)

count_using(10, 50)
  with_bill    = count_using(-40, 50)   → 0
  without_bill = count_using(10, 20)
  = count_using(10, 20)

count_using(10, 20)
  with_bill    = count_using(-10, 20)   → 0
  without_bill = count_using(10, 10)
  = count_using(10, 10)

真正的分叉从 count_using(10, 10) 开始：

count_using(10, 10)
├─ with_bill    = count_using(0, 10)  → remaining == 0 → 1   ★叶子1：一张 $10
└─ without_bill = count_using(10, 5)

   count_using(10, 5)
   ├─ with_bill    = count_using(5, 5)
   │  ├─ with_bill    = count_using(0, 5) → 1                ★叶子2：两张 $5
   │  └─ without_bill = count_using(5, 1)
   │     ├─ with = count_using(4, 1)
   │     │  └─ ... 一路 -1 ... count_using(0, 1) → 1         ★叶子3：一张$5 + 五张$1
   │     └─ without = count_using(5, None) → None → 0
   │     count_using(5, 1) = 1 + 0 = 1
   │  count_using(5, 5) = 1 + 1 = 2
   └─ without_bill = count_using(10, 1)
      ├─ with = count_using(9, 1) → ... → count_using(0,1) → 1  ★叶子4：十张 $1
      └─ without = count_using(10, None) → 0
      count_using(10, 1) = 1 + 0 = 1

   count_using(10, 5) = 2 + 1 = 3
count_using(10, 10)   = 1 + 3 = 4   ✓

四片「返回 1 的叶子」，正好是四种凑法，一一对应。 注意 count_using(x, 1) 这一支永远返回 1（只要 x >= 0）—— 道理很简单：用 1 元凑任何非负整数，方法唯一，就是全用 1 元。

把关键中间值列成表，方便对照：

同样的方法验 15：count_using(15, 1) = 1， count_using(15, 5) = 4（三张$5；两张$5+五张$1；一张$5+十张$1；十五张$1）， count_using(15, 10) = count_using(5, 10) + count_using(15, 5) = 2 + 4 = 6。✓ 而 count_using(5, 10) = count_using(-5, 10) + count_using(5, 5) = 0 + 2 = 2。 20、50、100 都太大，值一路保持 6。最终 count_dollars(15) == 6。

def count(状态, 当前可选项):
    if 成功:        return 1
    if 失败/耗尽:   return 0
    return count(用了当前选项后的状态, 当前可选项)      # 选项可重复用
         + count(状态不变,           下一个选项)      # 放弃当前选项

5. Shuffle：把序列的两半交错洗牌

题目要什么

shuffle(s) 接收一个元素个数为偶数的序列（sequence，可以是 list，也可以是 range）， 把它前一半和后一半的元素交错排列，返回一个新列表。 不修改 s。

「交错」的定义：新列表依次是 s0 的第 0 个、s1 的第 0 个、s0 的第 1 个、s1 的第 1 个…… 其中 s0 是前半，s1 是后半。

>>> shuffle(range(6))
[0, 3, 1, 4, 2, 5]
>>> letters = ['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']
>>> shuffle(letters)
['a', 'e', 'b', 'f', 'c', 'g', 'd', 'h']
>>> shuffle(shuffle(letters))
['a', 'c', 'e', 'g', 'b', 'd', 'f', 'h']
>>> letters  # Original list should not be modified
['a', 'b', 'c', 'd', 'e', 'f', 'g', 'h']

这个洗牌方式在扑克里叫 riffle shuffle（鸽尾式交错洗牌）： 把牌分成两摞，然后左一张右一张地交叉插进去。

要注意的几点：

• 输入可能是 range 而不是 list。第一个 doctest 就是 shuffle(range(6))。 所以你只能用「序列都支持的操作」：len()、s[i] 索引、切片。 不能用 s.append()、s.pop()——range 对象没有这些方法 （AttributeError: 'range' object has no attribute 'append'）。
• 必须返回新列表，不能改 s。最后一个 doctest （>>> letters 应仍是原样）就是专门测这一点的。
• 返回值必须是 list，不能是 range 或 tuple。 shuffle(shuffle(letters)) 这个嵌套调用说明返回值还要能再喂给 shuffle。
• 第一行 assert len(s) % 2 == 0 是题目给好的，不用动，它保证了「恰好能对半分」。

怎么想到的

这题没有递归，是纯粹的索引练习，但索引算错是最容易翻车的地方。 所以第一件事不是写代码，是把下标关系写在纸上。

拿 s = ['a','b','c','d','e','f','g','h']，len(s) == 8，half = 4：

规律一眼就出来了：成对出现——第 i 对是 (s[i], s[half + i])， i 从 0 走到 half - 1。

第二个问题：half 怎么算？len(s) // 2。 为什么是 // 而不是 /？ 因为 / 返回浮点数，8 / 2 == 4.0， 拿它当下标会报 TypeError: list indices must be integers or slices, not float。 虽然 assert 已经保证长度是偶数、除得尽，但类型仍然是 float。这是新手最常踩的坑之一。

第三个问题：怎么保证不修改 s？ 答案是根本不碰 s——只读它（s[i] 是读）， 所有写操作都发生在一个全新的空列表 shuffled = [] 上。 这里我走过一个弯路：一开始想写 shuffled = s 再原地调整， 但 shuffled = s 根本不复制，只是让两个名字指向同一个列表对象 （这叫 aliasing，别名）。往 shuffled 里 append， letters 也会跟着变长，最后一个 doctest 立刻失败。 要复制得写 list(s) 或 s[:]；但这题连复制都不需要，从空表建起最干净。

代码

def shuffle(s: list) -> list:
    assert len(s) % 2 == 0, 'len(seq) must be even'
    half = len(s) // 2
    shuffled = []
    for i in range(half):
        shuffled.append(s[i])
        shuffled.append(s[half + i])
    return shuffled

验证一：shuffle(range(6))

range(6) 的元素是 0,1,2,3,4,5，len == 6， 6 % 2 == 0 通过 assert，half = 3。 前半是 0,1,2（下标 0,1,2），后半是 3,4,5（下标 3,4,5）。

range(3) 到此耗尽，返回 [0, 3, 1, 4, 2, 5]。✓ 顺带注意：返回的是 list，不是 range， 所以 doctest 显示的是 [0, 3, 1, 4, 2, 5] 而不是 range(...)。

验证二：shuffle(shuffle(letters))

这是最能暴露理解深度的一个 doctest。先算内层：

letters   = ['a','b','c','d','e','f','g','h']     half = 4
  前半 = a b c d (下标 0..3)   后半 = e f g h (下标 4..7)
  i=0: append a, append e   →  [a, e]
  i=1: append b, append f   →  [a, e, b, f]
  i=2: append c, append g   →  [a, e, b, f, c, g]
  i=3: append d, append h   →  [a, e, b, f, c, g, d, h]

内层结果 t = ['a','e','b','f','c','g','d','h']

再对 t 洗一次：                                    half = 4
  前半 = a e b f (下标 0..3)   后半 = c g d h (下标 4..7)
  i=0: append t[0]=a, append t[4]=c  →  [a, c]
  i=1: append t[1]=e, append t[5]=g  →  [a, c, e, g]
  i=2: append t[2]=b, append t[6]=d  →  [a, c, e, g, b, d]
  i=3: append t[3]=f, append t[7]=h  →  [a, c, e, g, b, d, f, h]

结果 ['a','c','e','g','b','d','f','h']   ✓

然后 doctest 检查 letters 仍然是 ['a','b','c','d','e','f','g','h']。 为什么它没变？因为两次 shuffle 调用都只从 s 里读 （s[i]、s[half+i]、len(s)），所有 append 都作用在函数内部新建的 shuffled 上。

Global 帧
    letters ───→ ┌──────────────────────────────┐
                 │ list1: a b c d e f g h        │   ← 从头到尾没被改过
                 └──────────────────────────────┘

第一次调用 shuffle(letters):
f1: shuffle [parent=Global]
    s        ───→ list1        （只读）
    half     4
    shuffled ───→ ┌──────────────────────┐
                  │ list2: a e b f c g d h │   ← 新对象
                  └──────────────────────┘
    return value ───→ list2

第二次调用 shuffle(list2):
f2: shuffle [parent=Global]
    s        ───→ list2        （只读）
    shuffled ───→ ┌──────────────────────┐
                  │ list3: a c e g b d f h │   ← 又一个新对象
                  └──────────────────────┘
    return value ───→ list3

list1、list2、list3 是三个互不相干的对象。

6. Deep Map：就地改写嵌套列表

题目要什么

先看定义。嵌套数字列表（nested list of numbers）：一个列表， 它的元素要么是数字，要么还是嵌套数字列表。 [1, [2, [3]], 4]、[1, 2, 3]、[[1, 2], [3, 4]] 都算。

deep_map(f, s) 要就地（in place）把 s 里每一个数字 （不管埋在多深）替换成 f(那个数字)。

>>> six = [1, 2, [3, [4], 5], 6]
>>> deep_map(lambda x: x * x, six)
>>> six
[1, 4, [9, [16], 25], 36]

注意第二行调用之后什么都没打印——因为 deep_map 返回 None， 而交互式解释器不显示 None。效果全在 six 上，所以第三行才要重新求值 six。

题面里有两条硬约束：「deep_map returns None and should not create any new lists.」 后半句由这段 doctest 强制检查：

>>> s = [3, [1, [4, [1]]]]
>>> s1 = s[1]
>>> s2 = s1[1]
>>> s3 = s2[1]
>>> deep_map(lambda x: x + 1, s)
>>> s
[4, [2, [5, [2]]]]
>>> s1 is s[1]
True
>>> s2 is s1[1]
True
>>> s3 is s2[1]
True

这四行是全题的灵魂，必须逐字读懂。s1 = s[1] 让 s1 指向 s 里那个子列表对象本身（不是副本）。 调用 deep_map 之后再问 s1 is s[1]—— is 检查的是「是不是同一个对象」，不是「值是否相等」。 它为 True，就说明你没有把 s[1] 换成一个新造的列表， 而是钻进原来那个列表里把元素一个个改掉了。

还有一条提示：type(a) == list 在 a 是列表时为 True。 这是本题唯一需要的类型判断手段。

怎么想到的

第一反应多半是这样写：

# 错误示范 1
def deep_map(f, s):
    result = []
    for x in s:
        if type(x) == list:
            result.append(deep_map(f, x))
        else:
            result.append(f(x))
    return result

这是最自然的「map」写法，但它造了新列表， 既违反「returns None」也违反「should not create any new lists」。 s1 is s[1] 会是 False。

第二反应：那就 for x in s: x = f(x) 吧？

# 错误示范 2
def deep_map(f, s):
    for x in s:
        if type(x) == list:
            deep_map(f, x)
        else:
            x = f(x)

这个版本什么都不会发生，而且不报错，最阴险。 原因：for x in s 里的 x 只是一个局部名字， 每轮被重新绑定到列表里的下一个元素。 x = f(x) 只是把这个局部名字重新指向一个新数字， 列表本身的第 i 个槽位（slot）没被碰过。 循环一结束 x 就没了，改动随之蒸发。

有了这一点，剩下的就是递归的老三步：

对每个下标 i，看 s[i] 是什么：

情况 1: s[i] 是一个列表
    → 它内部可能还埋着数字，需要同样的处理
    → 递归：deep_map(f, s[i])
    → 注意：不接返回值！deep_map 靠副作用工作，
      它会钻进 s[i] 这个对象里把元素改掉，
      而 s[i] 这个槽位存的引用【一动不动】——这正是 `is` 测试要的。

情况 2: s[i] 是一个数字
    → 直接替换：s[i] = f(s[i])

还有一个我一开始没想明白的点：为什么递归调用不写 s[i] = deep_map(f, s[i])？ 因为 deep_map 返回 None，那样写会把子列表整个替换成 None， 结果变成 [4, None]。就地修改型的函数，调用它就完事了，不要接返回值。 这和 Q5 的 shuffle 恰好相反，两题放在一起就是要练这个对比。

代码

def deep_map(f, s: list) -> list:
    for i in range(len(s)):
        if type(s[i]) == list:
            deep_map(f, s[i])  # Recurse into the sublist, mutating it in place.
        else:
            s[i] = f(s[i])

验证：追踪 deep_map(lambda x: x + 1, s)，s = [3, [1, [4, [1]]]]

先把对象关系画清楚。调用之前：

Global 帧
    s  ──→ ┌───────────────────┐
           │ listA: [ 3 , • ]  │
           └───────────┬───────┘
                       ↓
    s1 ──→ ┌───────────────────┐
           │ listB: [ 1 , • ]  │
           └───────────┬───────┘
                       ↓
    s2 ──→ ┌───────────────────┐
           │ listC: [ 4 , • ]  │
           └───────────┬───────┘
                       ↓
    s3 ──→ ┌───────────┐
           │ listD: [1]│
           └───────────┘

s1 和 listA 的第 1 槽指向【同一个】listB。
s2 和 listB 的第 1 槽指向【同一个】listC。
s3 和 listC 的第 1 槽指向【同一个】listD。

现在跑递归。f = lambda x: x + 1：

deep_map(f, listA)                      len = 2, i 取 0, 1
  i=0: listA[0] 是 3，不是 list
       → listA[0] = f(3) = 4            listA 变成 [4, •→listB]
  i=1: listA[1] 是 listB，是 list
       → deep_map(f, listB)   ← 递归，【不】给 listA[1] 赋值

     deep_map(f, listB)                 len = 2
       i=0: listB[0] 是 1 → listB[0] = 2      listB 变成 [2, •→listC]
       i=1: listB[1] 是 listC → deep_map(f, listC)

          deep_map(f, listC)            len = 2
            i=0: listC[0] 是 4 → listC[0] = 5   listC 变成 [5, •→listD]
            i=1: listC[1] 是 listD → deep_map(f, listD)

               deep_map(f, listD)       len = 1
                 i=0: listD[0] 是 1 → listD[0] = 2   listD 变成 [2]
                 循环结束 → 隐式 return None
            循环结束 → return None
       循环结束 → return None
  循环结束 → return None

调用之后的对象图——箭头一根都没变，只有方框里的数字变了：

Global 帧
    s  ──→ ┌───────────────────┐
           │ listA: [ 4 , • ]  │        3 → 4
           └───────────┬───────┘
                       ↓  （还是原来那根箭头）
    s1 ──→ ┌───────────────────┐
           │ listB: [ 2 , • ]  │        1 → 2
           └───────────┬───────┘
                       ↓
    s2 ──→ ┌───────────────────┐
           │ listC: [ 5 , • ]  │        4 → 5
           └───────────┬───────┘
                       ↓
    s3 ──→ ┌───────────┐
           │ listD: [2]│                1 → 2
           └───────────┘

于是四个 doctest 全部满足：

再快速验第一个 doctest：six = [1, 2, [3, [4], 5], 6]，f = lambda x: x * x。 外层 len == 4：i=0 把 1 变 1；i=1 把 2 变 4； i=2 是列表 [3, [4], 5]，递归进去把 3 变 9、 再往里递归把 4 变 16、回来把 5 变 25，得到 [9, [16], 25]； i=3 把 6 变 36。最终 six 是 [1, 4, [9, [16], 25], 36]。✓

7. Count Dollars Upward（选做）：把方向反过来

题目要什么

和 count_dollars 完全一样的问题，唯一的区别是必须用 next_larger_dollar：

def next_larger_dollar(bill: int) -> int:
    """Returns the next larger bill in order."""
    if bill == 1:
        return 5
    elif bill == 5:
        return 10
    elif bill == 10:
        return 20
    elif bill == 20:
        return 50
    elif bill == 50:
        return 100

同样地，next_larger_dollar(100) 返回 None——没有更大的面额了。 doctest 的期望值和 Q4 一模一样：15 → 6，10 → 4，20 → 10，45 → 44，100 → 344，200 → 3274。

怎么想到的

这题真正在问的是：Q4 里「从大到小」这个方向，是本质的还是任意的？

答案是：任意的。防止重复计数的机关不是「大到小」，而是 「面额的考察顺序被固定住了，而且只能单向前进」。 方向朝上朝下都行，只要一致。

三个 base case 一个字都不用改，因为它们的含义与方向无关： remaining == 0 是成功、remaining < 0 是超支、 面额变成 None 是选项耗尽。

代码

def count_dollars_upward(sum_needed: int) -> int:
    def count_using(remaining, smallest_bill):
        """Ways to make `remaining` using bills no smaller than smallest_bill."""
        if remaining == 0:
            return 1
        elif remaining < 0 or smallest_bill is None:
            return 0
        with_bill = count_using(remaining - smallest_bill, smallest_bill)
        without_bill = count_using(remaining, next_larger_dollar(smallest_bill))
        return with_bill + without_bill

    return count_using(sum_needed, 1)

和 Q4 逐行对照，只有三处不同：

验证：count_dollars_upward(10)

期望仍是 4。但这次树的形状完全不同——先决定用几张 $1，再往上走。

count_using(10, 1)
├─ with_bill    = count_using(9, 1)
│                 ├─ count_using(8, 1) ... 一路 -1 ...
│                 │   最终 count_using(0, 1) → 1        ★十张 $1
│                 └─ 每一层的 without 分支都是 count_using(k, 5)，见下
└─ without_bill = count_using(10, 5)     ← 一张 $1 都不用

count_using(10, 5)
├─ with_bill    = count_using(5, 5)
│                 ├─ with    = count_using(0, 5) → 1     ★两张 $5
│                 └─ without = count_using(5, 10)
│                              ├─ with    = count_using(-5,10) → 0
│                              └─ without = count_using(5, 20) → ... 一路 <0 ... → 0
│                              = 0
│                 count_using(5, 5) = 1
└─ without_bill = count_using(10, 10)
                  ├─ with    = count_using(0, 10) → 1    ★一张 $10
                  └─ without = count_using(10, 20)
                               ├─ with = count_using(-10, 20) → 0
                               └─ without = count_using(10, 50) → ... → 0
                               = 0
                  count_using(10, 10) = 1
count_using(10, 5) = 1 + 1 = 2

那 count_using(10, 1) 呢？沿着 with_bill 一路减 1， 每减一次都会分出一个 count_using(剩余, 5) 的分支：

把这一列加起来：2 + 1 + 1（最后那个 count_using(0, 1)）= 4。✓ 四种凑法和 Q4 数出来的完全一样，只是被发现的顺序不同。

8. 整份作业回顾

六道必做题看着散，其实是一条严密的递进线。

三个可以带走的思维工具

本次作业的报错速查