08 尾调用：为什么递归可以是循环

栈帧存在的唯一理由

当你调用一个函数，机器必须记住一件事：「这家伙返回之后，我接着干什么？」

这个「接着干什么」被存在一个栈帧里。函数返回时，弹出栈帧，从里面掏出「接着干什么」，继续。

关键的问题是：有没有可能，根本没有「接着干什么」？

看这两个函数。它们做同一件事（1 加到 n），但结构不同：

; A · 非尾递归
(define (sum-to n)
  (if (= n 0)
      0
      (+ n (sum-to (- n 1)))))
;      ↑ 递归调用返回之后，还要做一次加法
;        所以这一帧「还有事要做」，不能走

; B · 尾递归
(define (sum-to n [acc 0])
  (if (= n 0)
      acc
      (sum-to (- n 1) (+ acc n))))
;     ↑ 递归调用的结果，就是本函数的结果
;       调用完直接返回，没有任何后续动作

◆ 尾位置（tail position）的定义

一个调用处在「尾位置」，当且仅当：它的返回值直接就是当前函数的返回值，中间不再经过任何计算。

换句话说：调用它，是这个函数做的最后一件事。

而这意味着：当前这一帧已经没用了。它里面存的「接着干什么」是空的 —— 它唯一要做的就是「把结果原样传回去」。

那还留着它干什么？直接把它覆盖掉，让新调用用同一块内存。

下面这台机器把两者并排画出来了。点「再递归一层」，看左右两边的栈：

Racket 的立场：这不是优化，是保证

这是最重要的一句话，也是最容易被误解的一句话：

◆ Proper Tail Calls 是语言标准的强制要求

Scheme / Racket 的语言标准规定：处在尾位置的调用必须复用当前栈帧。

这不是「编译器可能会帮你优化」，是「实现者不许不做」。一个不做尾调用的 Scheme 实现，不是 Scheme。

这个区别听起来学究，实际后果极大：因为它是保证，所以你可以依赖它来编程。Racket 程序员写循环的默认方式就是递归 —— 不需要祈祷，不需要检查编译器版本，不需要加关键字。

实测（本机 Racket v9.2）：

(define (loop n) (if (= n 0) 'done (loop (- n 1))))

(loop 10000000)     ; 一千万层
; ⇒ 'done           ; 秒回，内存纹丝不动

一个会颠覆你直觉的事实

现在看那个非尾递归的版本。按常识，它应该在几千层就爆栈，对吧？

(define (sum-to n) (if (= n 0) 0 (+ n (sum-to (- n 1)))))

(sum-to 100000)     ; ⇒ 5000050000      十万层，没事
(sum-to 1000000)    ; ⇒ 500000500000    一百万层，还是没事

一百万层非尾递归，Racket 眉头都不皱一下。

◆ 因为 Racket 的「栈」在堆上

JVM 和 V8 的调用栈是一块固定大小的连续内存（JVM 默认 512KB ~ 1MB）。用完就是 StackOverflowError，没得商量。

Racket 的续延（也就是「栈」）是堆上的数据结构，它能一直长，长到内存耗尽为止。

所以在 Racket 里，非尾递归的代价是 O(n) 的内存 —— 但不是崩溃。这是一个「慢慢变贵」而不是「突然死亡」的失败模式。

而这件事之所以可能，正是因为 Racket 把「接下来要做的事」做成了一等公民 —— 那个东西叫续延，是卷 IV 的主角。「栈」只是续延的一种实现方式，而且是一种很受限的实现方式。

所以「尾递归 vs 非尾递归」在 Racket 里的真正区别是：O(1) 空间 vs O(n) 空间，而不是「能跑 vs 崩溃」。这个心智模型比「会不会爆栈」更准确，也更有用。

你的语言呢？三种态度

JVM：做不到，而 Kotlin 想了个好办法

JVM 的字节码里没有「复用栈帧调用另一个方法」这条指令。这是一个二十多年的历史遗留问题（主要卡在栈帧检查和安全模型上）。所以 Java、Scala、Clojure、Kotlin 全都无法在 JVM 上直接实现尾调用。

Kotlin 的方案是绕过去：tailrec 关键字。

tailrec fun sumTo(n: Int, acc: Int = 0): Int =
    if (n == 0) acc else sumTo(n - 1, acc + n)

编译器看到 tailrec，会把这个递归改写成一个 while 循环。反编译一下：

// 反编译后（示意）
public static int sumTo(int n, int acc) {
    while (true) {
        if (n == 0) return acc;
        int newN = n - 1;
        acc = acc + n;      // ← 参数被就地更新
        n = newN;           // ← 然后 continue，帧被复用
    }
}

但真正聪明的地方在这里：

tailrec fun f(n: Int): Int =
    if (n == 0) 0 else 1 + f(n - 1)   // ← 编译器直接报错

warning: a function is marked as tail-recursive but no tail calls are found

◆ tailrec 为什么比「自动优化」更好

直觉上，「编译器自动检测并优化所有尾调用」听起来更好 —— 少写一个关键字嘛。但那是错的。

因为「这个调用到底在不在尾位置」是一件极易搞错的事，而搞错的后果是静悄悄的性能悬崖：你以为是 O(1)，实际是 O(n)，然后线上某个数据量大的用户把它跑爆了。

tailrec 的设计是：你声明意图，编译器验证意图。写错了当场告诉你。这是「让错误尽早暴露」原则的一次漂亮应用 —— 和第 24 章要讲的契约是同一种思路。

顺带一提，一个极易踩的坑：try/catch 里的递归调用不在尾位置（因为 catch 还等着接管呢），Kotlin 会拒绝把它当尾调用。这个坑在 Racket 里同样存在（with-handlers 里的调用也不是尾调用）。

JavaScript：规范里有，但没人实现（除了 Safari）

ES6（2015）的规范里明确写了 Proper Tail Calls。白纸黑字，是标准的一部分。

十一年过去了。实测 Node v24（2026 年）：

const sum = (n, acc = 0) => n === 0 ? acc : sum(n - 1, acc + n);
//                                        ↑ 教科书级的尾调用

sum(1000000);
// RangeError: Maximum call stack size exceeded

二分测出的爆栈深度：第 ~7811 层
Node 版本：v24.14.0

七千八百层。一个写得完全正确的尾递归函数。

只有 Safari 的 JavaScriptCore 实现了它。V8 团队实现过一版，然后撤回了 —— 理由是它会让调用栈信息丢失（调试时看不到完整的栈回溯），而且他们更倾向于一个需要显式语法的方案（return continue f() 之类），但那个提案一直没推进。

⚠ 这是一个值得记住的教训

「标准里写了」和「你能用」是两回事。

更重要的是：V8 的理由不是「做不到」，是「做了之后调试体验变差」。这是一个真实的工程权衡 —— 尾调用把栈帧吃掉了，而栈帧正是你调试时要看的东西。

（Racket 怎么解决这个矛盾的？它有 errortrace，在开发时插桩记录，代价是变慢。没有免费的午餐 —— 只有把成本挪到哪儿的选择。）

所以在 JS 里：老老实实用循环。递归只用在深度有界的地方（树、JSON），并且心里清楚那个界大概是七千。

怎么把递归改成尾递归：累加器模式

方法只有一个，而且它有个固定的形状：把「返回之后还要做的事」，提前做掉，塞进一个额外的参数里。

; 改造前：结果在「回来的路上」被拼出来
(define (sum-to n)
  (if (= n 0)
      0
      (+ n (sum-to (- n 1)))))       ; ← 回来还要加

; 改造后：结果在「去的路上」被拼好
(define (sum-to n [acc 0])           ; ← 多一个累加器
  (if (= n 0)
      acc                            ; ← 到底了，直接交出累加器
      (sum-to (- n 1) (+ acc n))))   ; ← 加法提前做掉了

看那个 (+ acc n)：它从「返回之后」搬到了「调用之前」。这样一来，调用就是最后一件事了。

再看一个（反转列表），同样的形状：

; 非尾递归：O(n²)，因为 append 每次都遍历一遍
(define (rev lst)
  (if (null? lst)
      '()
      (append (rev (cdr lst)) (list (car lst)))))

; 尾递归 + 累加器：O(n)，而且顺手就反转了
(define (rev lst [acc '()])
  (if (null? lst)
      acc
      (rev (cdr lst) (cons (car lst) acc))))
;                     ↑ 每次把头塞到 acc 前面 —— 天然反转

注意第二个版本不只是空间变好了，时间也从 O(n²) 变成了 O(n)。累加器模式经常有这种额外红利。

⚠ 但不要把所有递归都改成尾递归

这是新手学会尾递归之后最常犯的错。尾递归不是「更好的递归」，它是一个取舍：

它改变了计算的顺序。第 10 章你会看到：foldr（非尾递归）保持列表形状，foldl（尾递归）反转列表。想要保形，你就必须付出 O(n) 栈空间 —— 这不是缺陷，这是它在做的事情本身的代价。
树递归改不成尾递归。(+ (sum (left t)) (sum (right t))) —— 两个递归调用，最多只有一个能在尾位置。要真改，你得手动维护一个显式的栈，代码会变丑十倍，而且通常不值得（树的深度是 log n，不会爆）。
可读性。累加器版本永远比自然递归版本难读一点。如果深度有界（树、AST、JSON、配置文件），就用自然递归。

判据很简单：递归深度是不是由数据规模决定的？是（列表长度、循环次数）→ 必须尾递归。否（树的深度、嵌套层数）→ 别折腾。

哪些位置是尾位置？（这个表比你想的重要）

位置	是尾位置吗	为什么
`(if c A B)` 的两个分支	✓ 是	if 的值就是分支的值，没有后续计算
`(if C a b)` 的条件	✗ 不是	算完还要拿去判断
`(cond [c1 A] [else B])` 的结果	✓ 是	同 if
`(begin a b C)` 的最后一个	✓ 是	前面的都是副作用，最后一个的值就是结果
`(and a b C)` / `(or a b C)` 的最后一个	✓ 是	短路后最后一个的值就是结果
`(let ([x 1]) A)` 的函数体	✓ 是	let 的值就是体的值
`(+ 1 F)` 里的 F	✗ 不是	回来还要加
`(f G)` 里的 G（参数位置）	✗ 不是	回来还要调用 f
`(with-handlers (…) A)` 里的 A	✗ 不是	异常处理器还等着接管呢 —— 同 Kotlin 的 try/catch

记不住？有个万能判据：把调用换成一个 □，问自己「拿到 □ 的值之后，我这个函数还要做点什么吗？」

要做 → 不是尾位置。
直接把 □ 交出去 → 是尾位置。

（这个「□」不是随便画的。它就是第 13 章的主角 —— 你正在提前学习「续延」的概念，只是还没到给它起名字的时候。尾调用的本质是：这个调用的续延，恰好就是当前函数的续延，所以不需要新建一个。）

回流

⟲ 回流 · 三条能直接用的

① 在 Kotlin 里，遇到「深度由数据规模决定」的递归，一律加 tailrec。加不上（编译器报错）就说明你的递归不是尾递归，那你必须要么改成累加器形式，要么改成循环 —— 别侥幸。

② 在 JS/TS 里，不要指望尾调用。你的天花板大约是七千层，而且没有任何警告。处理可能很深的结构（长链表、深层 JSON、大图遍历）时，用显式的栈 + 循环：

// 递归版：深层 JSON 会爆栈
function walk(node) { node.children.forEach(walk); }

// 显式栈版：任意深度都安全
function walk(root) {
  const stack = [root];
  while (stack.length) {
    const node = stack.pop();
    stack.push(...node.children);
  }
}

你手动做的，正是尾调用优化做的事：把「隐式的调用栈」换成「显式的数据结构」。

③ 认出那个「累加器」，它到处都是。你在 Kotlin 里写的每一个 fold，在 JS 里写的每一个 reduce，参数里那个 acc —— 就是这个累加器。fold 就是「尾递归的循环」这个模式被抽象成的库函数。

这就是下一章的内容。

卷 II 结束

四章下来，那台机器的心脏你已经全看过了：

环境（第 5 章）：变量在哪儿，闭包记着谁
λ（第 6 章）：函数是值，而且函数足以造出一切
顺序（第 7 章）：先算参数；除非它是特殊形式
空间（第 8 章）：尾位置的调用不需要新帧

这四件事，就是一台求值器的全部零件。第 21 章你会用这四个零件，把它组装起来。

但在那之前，我们先去卷 III 练兵 —— 用这台机器解决真实的问题，并且带回一套你明天就能用在工作里的方法。