递归——Racket 处理列表与树的方式

递归不是 Racket 对循环的妥协，而是处理列表和树的自然方式——数据是递归的形状，处理就跟着是递归的形状。

你写过 for 循环、遍历过数组，习惯用「变量变化 + 条件判断」控制流程。到了 Racket，处理一串数据时，递归往往比循环更直接——不是 Racket 没有循环（for/fold、for/list 都在），而是列表和树本身就是递归结构。一个列表要么是空、要么是一个元素挂在更短的列表前面；一棵树要么是叶子、要么是一个节点挂着几棵子树。数据的形状决定了处理的形状——顺着形状拆，递归就是最短的路径。

这篇讲 Racket 里怎么用递归处理列表和树，以及怎么让它跑得跟循环一样快。

递归跟着数据的形状走

命令式语言里，循环跑在「变量变化 + 条件判断」上。Racket 不一样——递归建立在数据的形状上：

• 处理列表：拆成 (first lst) 和 (rest lst)
• 处理树：拆成当前节点和它的子节点
• 处理数字：拆成当前数和更小的数

递归之所以成立，是因为数据本身就有层级。Racket 的列表天然是递归结构——空列表是基础，非空列表是「一个元素 + 一个更短的列表」，用递归处理它几乎是本能。

一个递归函数永远有两个分支：基例（base case）回答最简单的情况，递归（recursive case）把问题缩小一步再交还给自己。计算列表长度就是这么一件事：

(define (length-of lst)
 (cond [(empty? lst) 0] ; 空列表长度为 0——基例
 [else (+ 1 (length-of (rest lst)))])) ; 否则 1 加上剩余部分的长度

(length-of '("a" "b" "c"))
;; 3

一个列表的长度，等于 1 加上剩余列表的长度。(empty? lst) 是结构上的终止点——到了空列表，就不再往下拆。

结构递归：照着列表拆开

上面这种「照着数据结构自然拆开」的写法，叫结构递归（structural recursion）。列表拆成首元素和剩余部分，你就在剩余部分上调用同一个函数——每一步都把列表变短，必然走到空列表。

再看一个例子，实现一个自己的 filter：

(define (my-filter pred lst)
 (cond [(empty? lst) '()]
 [else
 (define rest-filtered (my-filter pred (rest lst))) ; 先处理剩余部分
 (if (pred (first lst)) ; 再决定首元素留不留
 (cons (first lst) rest-filtered)
 rest-filtered)]))

(my-filter odd? '(1 2 3 4 5))
;; '(1 3 5)

结构递归不只对列表有效——二叉树、嵌套列表、自定义结构体，只要数据能拆成「当前部分 + 更小的同形部分」，都能套这个模式。它比命令式的循环更贴函数式编程的心智模型：不维护可变状态，只描述「这一步做什么」。

树：递归真正发力的地方

列表是线性的，递归只有一条路走到底。树才是递归真正闪光的地方——每个节点有任意多个子节点，循环要维护显式栈或队列，递归则直接交给调用栈。

定义一棵多叉树，求所有节点值的和：

(struct node (value children)) ; struct 自动生成 node-value、node-children 访问器

(define (tree-sum t)
 (+ (node-value t)
 (for/sum ([child (node-children t)]) ; 遍历子节点求和
 (tree-sum child)))) ; 每个子节点递归处理

(define demo-tree
 (node 1 (list (node 2 '())
 (node 3 (list (node 4 '()))))))

(tree-sum demo-tree)
;; 10 1 + 2 + 3 + 4

每个节点的和，等于当前值加上所有子节点的和。for/sum 把「遍历子节点并累加」压成一行，结构天然适合递归展开——你不需要自己管栈或队列。

尾递归：把递归跑成循环

回头看前面的 length-of：(else (+ 1 (length-of (rest lst))))——递归调用包在 +1 里，得等它返回才能做加法。这种「递归回来还要做事」的位置不是尾位置，每一层调用都占一帧栈，列表一长就可能溢出。

Racket 保证尾调用（proper tail calls）：递归调用若处在函数的尾位置——也就是整个分支的最后一步、后面不再有任何计算——Racket 就不为它分配新栈帧，而是复用当前这一帧。尾位置上的递归，不消耗额外栈空间，跑起来跟循环一样。

把「递归回来还要做的计算」提前做好，塞进一个累加器（accumulator）带下去，递归调用就挪到了尾位置。求和的尾递归版：

(define (sum lst acc)
 (cond [(empty? lst) acc]
 [else (sum (rest lst) (+ acc (first lst)))])) ; 递归调用是最后一步——尾位置

(sum '(1 2 3 4 5) 0)
;; 15

每一步把当前元素加进 acc，然后直接尾调用到剩余列表——没有「回来再算」的步骤。对一万个元素的列表，这版只占常量栈空间。

尾递归的套路就一句话：把「递归回来还要做的计算」提前算好，塞进累加器带下去，让递归调用成为最后一步。 它常用于累计计算、状态不断更新的算法，以及任何需要避免栈溢出的深度递归。

递归也能造结构

前面的例子都在「消耗」数据——读一个列表、算出一个数。递归还能反过来「生产」结构。构造一个从 n 倒数到 1 的列表：

(define (countdown n)
 (cond [(zero? n) '()]
 [else (cons n (countdown (sub1 n)))])) ; 把当前 n 挂到更小问题的结果前

(countdown 3)
;; '(3 2 1)

每一步把当前的 n 挂到更小问题的结果前面，递归到 0 时返回空列表——结构是「拼」出来的，不是「改」出来的。

把嵌套列表拍平，则是「边消耗边生产」的典型：

(define (flatten lst)
 (cond [(empty? lst) '()]
 [(list? (first lst))
 (append (flatten (first lst)) ; 首元素是列表，递归拍平后拼到前面
 (flatten (rest lst)))]
 [else (cons (first lst) ; 首元素是原子，挂到剩余结果前
 (flatten (rest lst)))]))

(flatten '((1 2) 3 ((4))))
;; '(1 2 3 4)

递归不只是读数据，也是造数据。

map、filter、fold 是命名好的递归

写到这儿你会发现，列表上的递归长得都差不多——拆首元素、递归处理剩余、按某种方式组合。Racket 标准库把这些常见模式封装成了高阶函数：map、filter、foldl、foldr。

理解了递归，这些工具就透明了——它们本质上都是命名好的递归模式。比如 foldr 的定义几乎就是你手写递归的样子：

(define (my-foldr f init lst)
 (cond [(empty? lst) init]
 [else (f (first lst)
 (my-foldr f init (rest lst)))])) ; 把 f 作用在首元素和「剩余折叠结果」上

(my-foldr + 0 '(1 2 3 4 5))
;; 15

任何能用 fold 表达的计算，都是递归的一种特化形式——你需要决定的只是「每一步怎么组合」，递归骨架 fold 已经替你写好了。

递归是一种拆问题的方式

掌握递归，不是背下几个例子，而是养成一种拆问题的方式：把问题分成更小的同类问题，在数据结构自然的边界上停下来，每一步都朝着更简单的方向走。一旦这种思维成型，大量算法——遍历、搜索、分治、回溯——都能自然地用递归描述。

找问题，再改对

两段都能跑、结果也对，但都把「递归回来再算」留在了尾巴上——一个慢，一个费栈。先说出各自的问题，再都改成尾递归：

1. 有人想反转一个列表：

(define (reverse-of lst)
  (cond [(empty? lst) '()]
        [else (append (reverse-of (rest lst))
                      (list (first lst)))]))

2. 有人想算 1 加到 n 的和：

(define (sum-1-to-n n)
  (cond [(zero? n) 0]
        [else (+ n (sum-1-to-n (sub1 n)))]))

改完想一想：你改后的两个版本，都多带了一个累加器。它替原来的递归干了一件什么事？为什么带上了它，递归就能「跑成循环」、不再一层层占着栈？

把列表看成「首元素加剩余」，把树看成「节点加子树」，把整个计算看成「问题一步步缩到基例」——递归就不再是玄学。