一个返回值正确的小规模递归，不一定能处理很深的输入。把计算包进函数，也不一定消除了调用栈增长。栈安全讨论的是执行策略：下一步计算发生时，前一步是否仍占着必须等待返回的栈帧。

本章在 Scala 3.3.7、Cats 2.12.0 和 Java 21 上比较普通递归、编译器可优化的尾递归、手写 Trampoline、Cats Eval，以及 Monad 的 tailRecM。统一深度为二十万。实验包含真实的 StackOverflowError 反例，也检查成功路径结果与分配观察，没有把“不爆栈”写成“没有空间成本”。

等待加法的递归栈

从一加到 n 的直接写法很短：

1
2
def unsafe(n: Int): Long =
  if n == 0 then 0L else n + unsafe(n - 1)

调用 unsafe(3) 时，外层需要等待 unsafe(2) 返回才能加三；下一层需要等待 unsafe(1) 才能加二。未完成的加法隐含保存在调用栈上。代码中的最后一个表达式虽然是加法表达式，但递归调用之后仍有工作，因此不是尾调用。

实验执行 unsafe(200000)，捕获 StackOverflowError 并断言确实发生。这个断言描述冻结运行环境上的现象，不给出普遍的最大递归深度。JVM 栈大小、编译状态和方法形状都可能改变首次溢出的位置。换环境后若二十万仍不溢出，应重新检查实验条件，不能伪造反例输出。

StackOverflowError 在本章只用于演示反例，不是业务流程中推荐的正常分支。生产程序不能靠捕获它反复尝试更小输入来管理任务，也不能在资源状态不明时假定所有清理都已可靠完成。深度可预见时应选择合适执行结构。

计算使用 Long 结果，并先把 n 转成 Long 再计算公式 n*(n+1)/2。若直接用 Int 计算二十万的平方，期望值自身可能溢出，导致“递归结果错误”的假报告。测试 oracle 的数值范围同样需要审查。

尾递归把未完成工作变成参数

把累加结果放进 acc 后，每一步只需要把新参数交给下一次调用：

1
2
3
@annotation.tailrec
def tailSum(n: Int, acc: Long): Long =
  if n == 0 then acc else tailSum(n - 1, acc + n)

acc 保存了此前完成的加法，递归返回后无需再做计算。注解要求编译器验证这种写法满足它的尾递归优化条件；它不是让任意递归自动变成尾递归的开关。将方法改回 n + tailSum(…)，应当重新面对编译诊断或栈增长，而不是保留注解当作证明文字。

对这个简单线性求和，尾递归或普通循环已经足够。引入通用解释器会增加类型和对象成本，没有必要为了使用库而替换所有循环。Trampoline 的教学价值在于展示控制流如何成为数据，并帮助理解后面更一般的组合链。

尾递归解决的是栈深度，不解决负输入、整数溢出或终止性。当前实验域是非负且固定为二十万的 n；若传入负数，n 不会按当前条件走向零。一个尾递归方法也可以无限循环，因此“编译器接受 tailrec”不是总函数证明。

将下一步表示为数据

手写 Bounce 只有两种状态：Done 包含最终值，More 包含一个返回下一段 Bounce 的零参函数。sum 不立即执行下一步，而是返回 More。

1
2
3
4
5
6
7
enum Bounce[A]:
  case Done(value: A)
  case More(next: () => Bounce[A])

def sum(n: Int, acc: Long): Bounce[Long] =
  if n == 0 then Bounce.Done(acc)
  else Bounce.More(() => sum(n - 1, acc + n))

解释器用 while 检查当前节点。遇到 More 时调用一次 next，把得到的新节点放回 current，再进入下一轮；遇到 Done 时返回值。关键在于每次 next 返回后，解释器才执行下一次，而不是 next 在返回前递归调用解释器。

1
2
3
4
5
6
7
def run[A](initial: Bounce[A]): A =
  var current = initial
  while true do
    current match
      case Bounce.Done(value) => return value
      case Bounce.More(next) => current = next()
  throw new AssertionError("unreachable")

局部 current 的更新不改变外部输入。解释器使用命令式循环，仍然可以执行一个对调用方表现为纯计算的描述。把函数式程序与“实现中不允许循环”绑定，会掩盖实际的栈安全机制。

对三步求和，run 依次看到 More、More、More、Done。中间每个 More 只描述一跳。这个最小类型没有提供任意 flatMap，也没有处理资源、异常恢复和取消。不能从它能执行尾式 sum 推导出已经实现了 Cats Eval 的全部组合能力。

如果错误地把 More 写成保存已经求出的 Bounce，而不是保存函数，构造过程就会立即递归，尚未进入 run 已经可能爆栈。延迟边界必须放在递归调用之前；只在最外层包一层函数，不会改变内部调用顺序。

一个会爆栈的 flatMap

实验故意实现 Naive。它延迟执行，但执行时仍通过嵌套函数调用展开整条链：

1
2
3
case class Naive[A](value: () => A):
  def flatMap[B](f: A => Naive[B]): Naive[B] =
    Naive(() => f(value()).value())

构造二十万个 flatMap 时不会运行 value，因而构造能够完成。但最后调用最外层 value，需要先调用上一层 value，再调用再上一层，直到最初节点。延迟了时间，没有消除嵌套调用栈。

实验断言这条链执行时发生 StackOverflowError。这个反例区分了三个概念：描述可以被保存，描述可以被组合，描述的解释是栈安全的。前两个条件都成立，第三个仍可能失败。

如果只测试十层链，Naive 和正确实现看起来没有区别。深链测试不是为了用大数字制造压力，而是要触发实现策略之间的差异。测试应保留具体深度和运行环境，同时避免宣称这个深度是所有环境的临界点。

为 Naive 增加 try/catch 不能修复控制流。修复需要把未完成绑定表示为数据，再用迭代解释器执行后续步骤；也可以使用提供栈安全组合的库。异常被捕获之后返回默认值，只会掩盖计算未完成。

Eval.defer 延迟递归构造

Cats Eval 的 defer 接收下一段 Eval 的延迟构造。当前实验写成：

1
2
3
def safe(n: Int): Eval[Long] =
  if n == 0 then Eval.now(0L)
  else Eval.defer(safe(n - 1)).map(_ + n)

safe(n-1) 没有在构造外层表达式时立刻递归。等解释器求值时再取得下一段，并由 Eval 的执行机制处理后续 map。实验调用 safe(200000).value，断言结果与尾递归、Trampoline 和独立公式相同。

如果改成 safe(n-1).map(_+n)，构造调用本身就会先不断深入，解释器来不及接管。defer 的位置因此属于正确性条件，不是可有可无的装饰。Cats 文档也特别区分构造递归与在求值中使用栈安全组合。Eval 文档

另一个测试从 Eval.now(0L) 开始，通过 foldLeft 构造二十万个 flatMap，每一步增加一，最后得到二十万。这与递归求和测试不同：前者检查已经建成的深绑定链，后者检查递归展开时是否正确延迟。只通过其中一个，不能覆盖另一个错误模式。

不要在 flatMap 回调里为了拿值而调用内层 .value，再把结果重新包回 Eval。那会提前执行内层描述，绕开原本的组合结构，并可能重新引入同步调用栈。外层保持 Eval 类型，让执行边界集中在最后一次 value，更容易分析。

Eval 并不自动管理任意回调内部的递归。若 map 中调用 unsafe(200000)，回调自身仍然使用普通调用栈。栈安全保证针对其组合机制，不意味着用户塞进去的任何同步程序都会被改写。

求值策略与重复观察

实验另建 Eval.later，在内部增加 laterCalls 并返回四十二。连续两次读取 value，结果都是四十二，计数为一。这个观察检查当前 later 的记忆化行为，不代表所有 Eval 构造方式都会缓存。

计数器在这里是测试探针，用来观察求值次数。实际代码如果要求引用透明，应避免把可变探针混进业务逻辑；若业务动作本身有副作用，更应明确它属于效果而不是普通值计算。Eval 的存在不会把任意副作用自动变成受资源管理的 IO。

重复使用描述时要先决定需求：希望每次重新计算，还是第一次计算后共享结果？选择不同策略会改变异常发生次数、读取外部状态的时刻和内存保留。不能仅凭变量类型为 Eval 就推断这些行为。

记忆化也会保留结果。一个很大的列表如果被 later 缓存，后续读取节约了计算，却可能延长列表寿命。当前四十二的测试不测空间，只验证次数。对于大型结果，应单独观察根引用与回收边界。

tailRecM 的两层结构

Monad 的 tailRecM 用一个状态 A 推进计算，步骤函数返回 F[Either[A,B]]。内层 Left 表示继续并给出下一状态，Right 表示完成；外层 F 保留具体上下文的行为。对于 Option，None 表示上下文中的缺席，不是“继续一步”。Cats Monad 文档

1
2
3
4
5
6
7
8
val result = Monad[Option].tailRecM(0) { i =>
  Some(if i < 200000 then Left(i + 1) else Right(i))
}
val stopped = Monad[Option].tailRecM(0) { i =>
  if i == 7 then None else Some(Left(i + 1))
}
assert(result.contains(200000))
assert(stopped.isEmpty)

第二个测试没有 Right。计算在状态七得到 None 后，整个 Option 结果结束。把 None 理解为再试一次，就会把正常短路变成无限循环。这里内层 Either 的 Left 不是业务错误，不能沿用普通错误处理教程里的直觉。

tailRecM 提供的是类型类要求的栈安全迭代接口。某个类型有名为 flatMap 的方法，并不能证明它的长链实现满足相同约束。手写实例时需要同时考虑组合定律、短路语义和执行栈，不能只写出类型签名。

本章只运行 Option 实例的两个场景。对 List、Either 或自定义效果，步骤展开数量和失败传播可能不同，应分别定义期望并测试。一个 Option 的成功证据不能替其他实例背书。

栈安全之后仍需计算空间成本

实验在建立 Eval 深链前后读取当前线程分配计数，断言增量大于零，并输出 chain-build-allocated-bytes。数值包含这个区间内链构造相关分配，不是每个 Eval 节点的精确大小。构建、解释和最终保留是三个不同阶段。

程序同时输出 retained-bytes=NOT_MEASURED。没有测量完整链求值后的精确存活堆，也没有比较 Trampoline 与尾递归的性能排名。不能用成功执行二十万层推导出 O(1) 堆空间，更不能把“栈不会线性增长”简写成“空间常量”。

手写 Bounce 在当前线性执行中，每一步只需要当前节点和下一步，但仍会创建许多短命节点与闭包。Eval 深 flatMap 链在执行前已经保留了大量组合节点。两者都避免了相同形式的 JVM 栈增长，却具有不同分配和可达图。

尾递归累加器通常是本问题更直接的实现。若需求只是一条简单计数循环，没有必要以通用组合结构换取已经拥有的能力。只有当计算需要被组合、延迟或通过通用接口解释时，额外结构才可能值得承担。

本章的分配计数没有预热和多轮统计，因此只用来确认分配确实存在，不报告性能优劣。与性能章节的计时协议混用，会把不同证据强度的观察写成同一种结论。要比较吞吐量，应另建同输入、同观察、同预热策略的实验。

失败、终止与资源不由栈安全保证

一个 tailRecM 步骤如果永远返回 Some(Left(…))，即使不爆栈，也不会完成。一个 Eval 回调如果阻塞等待外部连接，栈安全不会给它增加超时。一个 More 捕获文件句柄，解释器也不会自动关闭它。

这些边界说明控制流变成数据只是设计的一部分。终止需要输入域或度量递减；资源需要作用域；异步取消需要任务归属。不能把 Trampoline 当成一个简化版完整效果运行时。

普通异常在本章成功路径中没有被建模成 Either。若 sum 的下一步抛出异常，run 会把它传播给调用方。给 Bounce 增加失败分支可以让错误成为数据，但还需要决定回调异常是否捕获、在哪里捕获以及如何恢复。这是新的契约，不是简单增加一个 case 名称即可完成。

同样，观察顺序需要保护。将递归后加法改为累加器形式，对整数加法当前范围可得到同样结果；对浮点运算、字符串拼接或外部日志，重新组织顺序可能产生不同观察。栈安全改写仍要以业务等价为前提。

构造阶段和解释阶段分别画调用关系

分析一个延迟类型时，可以先忽略值，只追踪“谁在等待谁”。构造 Naive 链时，foldLeft 每次返回一个新闭包，没有调用旧闭包，因此构造栈不会随着已经建立的链长同步增加。执行最外层时，闭包先调用前一层 value，前一层又调用更早一层；这些调用都没有返回，于是执行栈增长。

Bounce 的线性 sum 则相反：构造只建立当前一跳，run 调用 next 后拿到下一节点，此次调用已经返回，再从 while 顶部继续。即使逻辑上走过二十万步，解释器也不需要保留二十万个等待 next 返回的 Java 栈帧。状态保存在当前节点和累加参数中，而不是隐含在递归返回地址里。

Eval 的深 flatMap 例子在构造时保存待执行的绑定关系。栈安全解释器需要以显式结构处理这些关系，而不是让每个节点通过普通方法递归求出父节点。本章没有重写 Cats 内部解释器，因而不报告它每一步的内部节点数；实际可验证的事实是同样深度下深链完成，并且结果正确。

这三个过程解释了为什么“延迟”“懒加载”和“栈安全”不能互作同义词。延迟回答何时开始求值，记忆化回答完成后是否复用结果，栈安全回答组合的执行是否需要随深度增长的调用栈。一个实现可以同时具备其中任意几个，而缺少其他能力。

累加器改写需要保持观察顺序

当前求和使用在已声明范围内不会溢出的 Long 加法，尾递归累加与直接递归得到同一数学结果。若操作换成减法，不能只把 acc+n 改成 acc-n 就假定与递归后做减法一致。必须先展开三个元素，观察括号位置，再写出新的状态更新规则。

例如右侧嵌套的减法与从左到右累加具有不同结合方向。把递归改写为循环时，需要显式保存原来的待执行操作，或证明新的累计结构与原表达式等价。这正是一般 Trampoline 需要继续计算结构，而简单尾累加器不能处理所有表达式的原因。

如果回调写日志，执行顺序本身就成为结果的一部分。普通递归可能先深入到底再记录，累加器版本可能边前进边记录。即使最终数值相同，两条事件序列也不同。测试应根据接口承诺选择是否比较日志，不能在改写之后才宣布这些观察无关。

浮点加法也需要谨慎。有限精度下重新分组可能改变舍入，因此用数学结合律推导任意机器数实现等价并不可靠。本实验使用受限整数输入，刻意避免把数值稳定性问题混进控制流演示。扩展到浮点聚合时，应另设误差模型或精确结果要求。

深度测试如何保持可诊断

正常成功路径与预期溢出路径放在同一个可重复入口中，但断言含义相反。unsafe 和 Naive 必须暴露溢出，tailSum、run、safe、深 Eval 链与 tailRecM 必须完成。若删除前两个负例，成功路径仍然能证明当前深度可运行，却失去了验证测试能够识别非栈安全实现的对照。

捕获范围只围住预期失败的表达式。不能在整个 main 外面捕获 StackOverflowError 后打印 PASS，否则安全实现意外溢出也会被当成反例成功。错误归属需要由代码作用域表达，不能靠人工阅读最后一行日志猜测。

环境变化时，应先检查 JDK、Scala、Cats 和启动参数，再判断失败是否来自实现。二十万是这里选定的压力深度，不是协议要求所有机器都在同一点耗尽栈。对于实际库回归，可以使用更系统的多深度序列；本文没有运行这种序列，因此没有绘制随深度变化的曲线。

另一个诊断维度是异常发生时机。缺少 defer 往往在构造 safe 描述时失败；Naive 在构造完成后的 value 才失败。把构造与求值放在不同的观察区间，有助于发现错误的延迟位置。只在最外层记录“程序失败”会丢失这个重要差别。

最终结果也必须校验。一个错误解释器可以通过提前返回零避免爆栈，甚至显得更快，但它没有完成计算。当前每个成功实现都与明确公式或步数比较，因此“退出正常”不能代替“执行正确”。栈安全与业务结果是两个同时需要满足的条件。

栈大小配置也不是通用修复。增加线程栈可能让同一输入暂时通过，却仍保留随深度增长的需求，并增加每个线程的资源预算。当前实验没有修改栈大小来掩盖失败，而是比较执行结构；若实际需求只有严格的小深度上限，直接递归也可能是可接受选择，但上限应进入输入校验与测试。

对于无法预先限制深度的外部树或表达式，显式工作栈还需要容量政策。把调用栈迁移到堆上的待办列表，只是让结构可控制，不会取消资源上限。需要决定超过预算时拒绝、分批还是终止，而不是把任何输入都交给无限增长的解释器。

与旧文、源码和练习的对应

旧文纯函数、递归与尾调用已经区分纯度与尾递归，并提醒固定宽度数值的溢出。本章不把它重讲成“递归优于循环”，而是增加延迟但不栈安全的 Naive 反例，以及 Eval 深链和 tailRecM 的真实执行。

完整 Main.scala包含上述实现及冻结依赖；运行证据记录二十万深度、两个溢出反例、成功结果、分配观察和源码散列。执行：

1
node examples/functional-programming/run.mjs 37

手算题：写出 sum(3,0) 被 run 解释时每个节点保存的 n 和 acc；再写出 tailRecM 在零到七短路场景中最后一次步骤返回的完整类型和值。前者依次推进到 Done(6)，后者返回 None，而不是 Some(Right(7))。

修改题：在 Eval.defer 的安全版本旁增加缺少 defer 的构造反例，保留原实现并分别记录“构造失败”和“执行失败”。然后给 sum 的公开入口增加负输入拒绝，确认没有把非法输入留成无限推进。不要把反例替换成打印字符串，也不要降低深度直到错误消失后声称栈安全。

另一个修改方向是给 Bounce 增加任意 flatMap。先让二十万次左关联组合成为回归，再设计解释器；如果实现只是递归调用已有 value，Naive 反例已经说明这种方案缺少什么。能够清楚指出继续计算保存在哪里，比单纯背出 Trampoline 的名字更接近掌握这个机制。