同样两件商品，为什么两次计算价格不同

一个价格函数接收数量，却从外部可变变量读取单价。第一次单价一百分，两件得到二百分；随后外部把单价改成二百分，传入同样数量就得到四百分。函数签名没有显示这个额外输入，所以仅靠参数无法重现结果。

另一种问题发生在递归汇总。对三条订单行，递归相加很直观；对十万条输入，若每层都要等待下一层返回后继续加法，调用栈可能持续增长。给方法加上尾递归注解并不能把任意递归变成循环，必须先改变计算结构。

本章固定 Scala 3.3.7、标准库 2.13.16、JDK 21，分别检验显式状态传递、局部可变实现、尾位置及大输入结果。纯函数与尾递归解决不同问题：前者关注可观察依赖，后者关注自递归控制流。一个尾递归方法仍然可以读取全局变量，一个纯函数也仍然可能使用过深的非尾递归。

把隐藏状态变成显式输入和输出

1
2
3
4
5
6
7
8
case class Cart(total: Long)
def add(cart: Cart, amount: Long): Cart =
  Cart(cart.total + amount)

val old = Cart(100)
val updated = add(old, 200)
assert(old == Cart(100))
assert(updated == Cart(300))

add 不修改传入购物车，而是返回新的总额值。输入旧购物车和新增金额足以说明当前实现如何计算结果。保存 old 后再次调用，仍能得到相等的 updated。这个对照把“旧状态是什么、新状态是什么”直接放在类型和参数中，便于重放与测试。

引用透明性的实用判断是：在讨论的观察范围内，能否用一个表达式的结果替换该表达式而不改变程序行为。若表达式读取时钟、随机数、可变费率或执行打印，替换之后可能减少一次读取或副作用，因此不能只看返回值类型相同。

这里还必须明确相等与身份的观察边界。两次创建值相等的购物车可能是不同引用，如果调用方故意用 eq 观察分配身份，就引入了值语义之外的差异。讨论纯值计算时通常把值相等作为主要观察；需要身份语义的对象则应显式处理，而不是把所有对象构造简单贴上同一标签。

固定宽度加法也有业务限制。Long 能表达当前实验总额，但不自动检测溢出。把状态改成显式参数消除了隐藏费率依赖，不意味着金额公式、边界检查和币种规则已经正确。纯函数使错误更容易复现，仍需要正确领域规则。

副作用留在需要执行的边界

真实订单系统必须读取文件、查询报价、保存结果。纯计算不是要求删除这些动作，而是把获取输入、计算决策、提交副作用分开。读取到的单价成为价格函数参数，计算返回待保存的订单结果，外围决定何时写入。

这样做能让同一业务函数接收固定测试输入，而不依赖网络是否可用。失败也可以成为显式返回值，说明当前输入无法形成合法结果。但如果函数仍隐式调用远程接口，或从对象字段读取可变缓存，签名上的显式参数就不完整，需要继续查找实际依赖。

纯核心还不能保证提交成功。计算得到新购物车，并不等于数据库已经写入；重试同一计算很容易，重试付款副作用则可能重复扣款。重算与重放副作用应有不同协议，幂等标识和事务边界仍然属于执行层。

日志同样是一种观察。把每一步调试打印放在原本纯粹的金额函数中，会使缓存、重复调用和重构改变日志次数。若日志只用于实验计数，可以明确它是观察装置；生产日志若有业务意义，就应放在清楚的执行边界，避免被无意重排。

局部变量不一定破坏对外的值语义

1
2
3
4
5
6
7
def loop(values: List[Int]): Long =
  var rest = values
  var acc = 0L
  while rest.nonEmpty do
    acc += rest.head
    rest = rest.tail
  acc

rest 和 acc 每次调用都重新创建，没有通过闭包、全局字段或返回值暴露给其他调用者。方法只读输入列表，返回累计值。就这份实现的对外结果而言，局部可变状态是内部计算手段，并不会让后一次调用继承前一次进度。

如果把 acc 提升为对象字段，或者返回一个能继续修改它的闭包，情况就不同。现在两次调用可能共享状态，执行顺序开始影响结果。判断是否有隐藏依赖应沿引用是否逃逸分析，而不是简单统计源文件里有几个 var。

局部 builder 也遵循这个思路。构建期间用可变缓冲，结束后发布独立稳定结果，可以兼顾接口清楚和构建成本；若发布的仍是同一可变对象，则调用方拿到的是共享修改通道。接口承诺需要和最终返回对象的实际性质一致。

测试等价时应保持输入相同。若第一种实现消耗了 Iterator，再让第二种实现读取同一个游标，第二次看到空输入，不是算法错误。本章使用可重复读取的不可变 List，确保尾递归与循环比较的是同一份元素序列。

非尾递归为何保留待完成的工作

考虑 head + sum(tail)。调用 sum(tail) 返回之后，当前方法还要把 head 加到结果上，所以递归调用不是最后一步。三项输入可以展开为一加上二加上三加零，每一层都保存尚未完成的加法。

尾递归改用累加器，把已经处理的部分汇总为参数。处理一项就把它加到 acc 中，然后递归调用剩余列表；递归返回之后不再执行额外计算。全部待保留状态都已经进入新参数，因此控制流有机会改成更新参数后跳回循环起点。

1
2
3
4
5
6
7
import scala.annotation.tailrec

@tailrec
def sum(values: List[Int], acc: Long = 0L): Long =
  values match
    case Nil => acc
    case head :: tail => sum(tail, acc + head)

输入一、二、三时，参数序列依次是完整列表与零、二三与一、三与三、空列表与六。每一步都满足同一不变量：acc 等于已消费前缀之和，values 是尚未消费的后缀。终点返回 acc，不再需要恢复原来各层的 head。

递归正确性与尾位置可以分别审阅。把 acc + head 错写成 acc - head，依然可能是合法尾递归，却得到错误业务结果。反过来，普通递归求和在小输入上结果正确，也不能证明大输入栈空间安全。注解和断言分别检查两种问题。

@tailrec 是编译检查，不是任意尾调用优化承诺

冻结编译器的 TailRec 阶段识别可转换的自递归尾调用，并把它们改写成更新局部参数与循环跳转的结构。注解要求目标方法符合相应条件；如果递归调用之后还要做加法，就报告该调用不在尾位置。

本章的负例给普通递归求和加上 @tailrec，预期编译失败且诊断包含 not in tail position。它没有通过故意构造栈溢出去证明问题，因为触发阈值取决于运行时栈大小和实现。编译诊断直接检查所讨论的结构约束，更适合这个验收目标。

这项转换不是 JVM 对任何尾调用的普遍支持。两个方法互相递归，即使各自最后一步是调用对方，也不能直接套用同一个自递归改写结论。可重写的方法、接收者和其他控制结构还可能增加限制，遇到注解失败应检查编译器原因，而不是去掉注解就称为修复。

尾递归也不保证终止。如果递归参数没有朝终点推进，循环化之后仍会一直执行；如果每步把对象加入全局集合，堆内存仍可能增长。栈空间、堆空间和终止性是三个独立维度。把“栈安全”写成“不会耗尽资源”会越过实际证据。

大输入验证结果，源码解释改写边界

正常程序汇总一到十万，尾递归与局部循环都得到五十亿零五万，即 5000050000L，并对空列表得到零。结果超过 Int 的正范围，所以累加器显式使用 Long；这也让类型选择与测试输入形成实际联系，而不是只在注释中声称支持大数。

运行通过说明本次输入在固定环境中完成，没有观察到递归栈失败。它不证明任意输入规模都能完成：构造十万项 List 本身已经消耗堆，输入再大可能受内存或时间限制。正文的尾调用机制依据来自冻结源码，运行是对具体程序的交叉验证。

同一程序另外保存读取可变 rate 的闭包。先用费率一百计算两件，再把费率改成二百，结果从二百变四百。这个反例与尾递归无关，专门说明参数未列出的状态会破坏重放假设。将 rate 改成显式参数后，输入记录才足以解释两个结果为什么不同。

把递归改成累加器时检查运算方向

求和常让改写看起来过于简单，因为加法的组合性质掩盖了一些错误。若原递归是在返回途中拼接文本、构造树或执行带顺序的操作，把工作提前放入累加器可能翻转顺序。应先写三项输入的中间状态，确认结果结构保持一致。

例如逐项把元素头插到累加列表，最终得到逆序；如果需要原顺序，还要在终点反转一次。这个额外反转是算法的一部分，不能因为末尾调用已是尾递归就省略。若运算不具备所需结合性质，也可能无法用一个简单标量累加器保持原语义。

这条方法可以迁移到状态机和解析器：明确当前状态、未处理输入以及终止条件，再判断递归调用后是否还有工作。只有把这些工作纳入状态或重新组织控制流，注解才有可能通过。注解是对改写结果的检查，不负责替开发者选择正确状态表示。

手算与修改练习

手算：sum(List(2,4),10) 返回多少？答案是十六，因为初始累加器十也参与结果。默认参数零只是常用入口，不表示任意调用都从零开始。若希望外部只看到普通求和接口，可以把带 acc 的辅助函数放到内部。

修改练习：用尾递归把列表反转，累加器是结果列表，遇到 head 就执行 head :: acc。输入一二三应得到三二一，空输入得到空。再实现保持原顺序的映射：先头插映射结果，再在终点反转，新增两项不同值防止顺序错误。为辅助函数加 @tailrec，并保留非尾求和的失败样例，确认注解仍在检查目标规则。

实验记录与依据

入口 scalaexamples.Chapter14，源码 examples/scala-lab/snippets/14/Chapter14.scala；实际命令和结果见 RUN.md。

  • 冻结 TailRec.scala：核对自递归尾位置及循环改写，不把整段实现推广为一般 JVM 能力。
  • tailrec 2.13.16 API：核对注解的编译检查用途。
  • List 2.13.16 API：核对本章输入结构。显式状态、前缀不变量和循环对照为独立实验推导。

前置阅读：for 推导式。

顺序导航：系列入口：00 · 上一篇：13 · 下一篇：15。