结构化递归：一套可以带走的设计配方

一个你可能没意识到的事实

「列表」这个东西，它的定义是递归的：

注意第二条里的「另一个列表」—— 定义在引用它自己。这就是为什么 '(1 2 3) 其实是：

'(1 2 3)
= (cons 1 '(2 3))
= (cons 1 (cons 2 '(3)))
= (cons 1 (cons 2 (cons 3 '())))
;                            ↑ 最后总是那个空表

现在是关键的一跳：

于是，处理任何列表的函数，骨架必然是这样：

(define (处理列表 lst)
  (cond
    [(null? lst) ...]                       ; 情况一：空表
    [else (... (car lst)                    ; 情况二：头
               (处理列表 (cdr lst)))]))      ;         和「尾巴处理完的结果」

这个骨架里只有三个洞。而填这三个洞，比从零开始想「怎么写这个函数」容易一个数量级。

试一遍：求和

(define (sum lst)
  (cond
    [(null? lst) 0]                          ; 空表的和 = 0
    [else (+ (car lst) (sum (cdr lst)))]))   ; = 头 + 尾巴的和

三个洞填完了。而且填的时候，你每次只需要回答一个非常局部的问题：

• 「空表的和是多少？」 → 0。（不需要想递归。）
• 「假设尾巴的和我已经算出来了，怎么得到整个列表的和？」 → 加上头。（不需要想它是怎么算出来的。）

完整的设计配方（六步）

HtDP 把这套东西固化成了一个流程。它看起来很啰嗦，但请你至少在真实工作里试三次 —— 你会发现自己盯着空白编辑器发呆的时间大幅减少。

走一遍完整的。需求：算一个文件树的总大小。

第 1 步：数据定义

; 一个 条目（Entry）要么是：
;   - 文件：有名字和大小
;   - 目录：有名字，和一个「条目列表」   ← 注意这里是递归的！

(struct file (name size) #:transparent)
(struct dir  (name kids) #:transparent)   ; kids 是 Entry 的列表

停一下，看清楚这个定义里藏了什么：

• 「条目」有两种形态 → 代码会有两个分支
• 目录里含有「条目的列表」→ 会需要两个互相调用的函数（一个处理条目，一个处理列表）

这些结论我还一行代码都没写就已经知道了。这就是配方的价值。

第 2 步：签名 + 目的

; total-size : Entry -> Number
; 算出一个条目（文件或整个目录树）占用的总字节数

第 3 步：例子（先写！）

(require rackunit)

(define fs
  (dir "root" (list (file "a" 10)
                    (dir "sub" (list (file "b" 20)
                                     (file "c" 5)))
                    (file "d" 1))))

(check-equal? (total-size (file "x" 7)) 7)       ; 单个文件
(check-equal? (total-size (dir "empty" '())) 0)  ; 空目录 ← 边界！
(check-equal? (total-size fs) 36)                ; 10 + 20 + 5 + 1

注意那个空目录。你是在写例子的时候想到它的，不是在写代码的时候 —— 这就是「先写例子」的价值：它逼你在写实现之前面对边界情况。

第 4 步：模板（机械地抄）

; 从数据定义抄：两种形态 → 两个分支
(define (total-size e)
  (cond
    [(file? e) ... (file-size e) ...]     ; 文件里有什么，就写出来
    [(dir? e)  ... (dir-kids e) ...]))    ; 目录里有一个「列表」→ 需要辅助函数

; 从「列表」的定义抄：空 / 非空 → 两个分支
(define (total-size-list lst)
  (cond
    [(null? lst) ...]
    [else ... (total-size (car lst))          ; 头是一个 Entry → 调 total-size
           ... (total-size-list (cdr lst)) ...]))  ; 尾是一个列表 → 调自己

看清楚这一步：我完全没有思考「怎么算文件大小」这个问题。我只是盯着数据定义，把它的形状抄了下来。递归调用出现在哪里，是数据定义告诉我的 —— 「这里有一个 Entry」→ 调处理 Entry 的函数；「这里有一个列表」→ 调处理列表的函数。

第 5 步：填空

(define (total-size e)
  (cond
    [(file? e) (file-size e)]
    [(dir? e)  (total-size-list (dir-kids e))]))

(define (total-size-list lst)
  (cond
    [(null? lst) 0]
    [else (+ (total-size (car lst))
             (total-size-list (cdr lst)))]))

第 6 步：跑

> (total-size fs)
36                    ; ✓ 和第 3 步写的例子一致

为什么你在工作里常常写不出来

诚实地说：你在真实工作里，八成不会走这六步。你会直接开始写。

而当你卡住的时候，八成是因为你跳过了第 1 步。

「这个函数怎么写」这个问题之所以难，往往是因为你还没搞清楚「我在处理的到底是个什么形状的东西」。而一旦你把数据的形状写清楚 —— 它有几种情况？每种情况里有什么？哪些字段又是复合结构？—— 代码骨架就没什么可想的了。

下次你盯着编辑器发呆的时候，试试关掉编辑器，先在纸上写清楚：

• 输入有几种形态？（这决定了你有几个分支）
• 每种形态里有什么字段？（这决定了你能用什么）
• 哪个字段的类型「又是它自己」或者「是它的列表」？（这决定了递归调用出现在哪里）

回流：你的语言里，这套配方叫什么

// 第 1 步：数据定义（有几种形态？）
sealed interface Entry
data class MyFile(val name: String, val size: Long) : Entry
data class Dir(val name: String, val kids: List<Entry>) : Entry
//                                        ↑ 递归！

// 第 4 步：模板 —— IntelliJ 会帮你生成所有分支（Alt+Enter → add remaining branches）
fun totalSize(e: Entry): Long = when (e) {
    is MyFile -> TODO()
    is Dir    -> TODO()
}
// ↑ 如果你漏了一个分支，编译器直接报错（when 用作表达式时必须穷尽）

// 第 5 步：填空
fun totalSize(e: Entry): Long = when (e) {
    is MyFile -> e.size
    is Dir    -> e.kids.sumOf { totalSize(it) }   // 列表 → sumOf 替你做了递归
}

type Entry =
  | { kind: "file"; name: string; size: number }
  | { kind: "dir";  name: string; kids: Entry[] };   // ← 递归

function totalSize(e: Entry): number {
  switch (e.kind) {
    case "file": return e.size;
    case "dir":  return e.kids.reduce((a, k) => a + totalSize(k), 0);
  }
}
// 想要穷尽检查？加一个 default: const _x: never = e; —— 漏分支时类型报错

这一章的一句话

你不是在「设计代码」，你是在「阅读数据的形状，然后把它抄下来」。

灵感是稀缺的，而配方不是。把需要灵感的部分压缩到最小 —— 这就是工程和艺术的区别。

下一章，我们会发现：连这个「模板」本身，都可以被抽象掉。它有一个名字，你天天在用它：fold。