递归模式的隐秘历史

TL;DR：从面条式 goto 到结构化循环，再到尾递归，最终到递归方案，这场演讲追溯了我们如何学会用数学方式描述迭代，以及为何大多数语言仍把最好的抽象藏了起来。 ## goto 深渊与结构化之路 条件分支赋予计算机力量，但裸机级的跳转会缠成难读的“意大利面条”。 早期程序员别无选择——直到 Fortran 54 带来符号表达式和自动寄存器分配，用 20% 的性能换取 5 倍开发速度和 20 倍代码压缩。 C 只多了指针和更大的生态；真正价值在于编译器管理的“无限寄存器”。然而我们仍保留无限制 goto。Dijkstra 1968 年的信指出：goto 密度与代码质量成反比——不受限的跳转抹掉了推理中间状态的坐标系。唯一可原谅的用法是：程序已注定失败时，向前跳转到单个清理标签。 Linux 里依旧 goto 遍地，说明内核开发者不信任编译器，乐于“裸骑硅片”。把编译器锁死在刚性控制流图上，会把意图冻在低层细节里，也失去让编译器变好的压力。 ## 用方程代替循环 要让进展可见，我们把循环写成方程：把初值、更新函数、退出测试打包成一个自包含的**函数**。 若函数以自调用收尾，就是**尾递归**，靠谱编译器会把它变成跳转。老 C 编译器没做到，于是 Java 阵营仍念咒“递归跳湖去吧”。现代 GCC 与 Clang 已优化尾调用——只小心 Python，它明令禁止 TCO 以保留完整栈追踪。 看生成的汇编：GCC 假装优化尾递归版 Collatz，却直接返回 1（利用“无限递归未定义”），而 Clang 吐出干净循环。教训：在意循环形状就写尾递归，或至少写 do-while。 ## tailRec：一个组合子统治全场 在 Haskell 里，我们可以一次性捕获模式： ```haskell tailRec :: (s -> Either r s) -> s -> r ``` 种子 `s` 要么被新种子替换（`Right`），要么产出最终结果（`Left`）。 Collatz 写成： ```haskell collatz = tailRec $ \n -> if n == 1 then Left 1 else Right (if even n then n `div` 2 else 3 * n + 1) ``` 结构——种子类型、退出测试、更新——一行声明；干活的是纯函数，可组合。想加副作用用 `tailRecM`： ```haskell tailRecM :: Monad m => (s -> m (Either r s)) -> s -> m r ``` `tailRec` 只适用于**定长状态**；不分配无界内存，性能可预测。多数语言，哪怕支持高阶函数，也不自带这个组合子——Scala 抄了 Haskell 的 `recursion-schemes` 库，只是例外。 ## 当数据本身也递归 朴素递归求和会把整个列表骨架留在栈上。 尾递归能解决栈问题，却得把累加器和剩余列表搓成一对，“把圆钉敲进方孔”。真正的洞见：**控制结构应镜像数据结构**。 递归数据类型如 ```haskell data List a = Nil | Cons a (List a) data Rose a = Node a [Rose a] ``` 由构造子定义，用模式匹配消费。我们需要的是能**遍历**这些形状、同时管理累加器、副作用与提前终止的组合子——比 `tailRec` 丰富，却同样通用。这“更丰富的家伙”就是**递归方案**家族，主流语言仍把它藏起来的隐藏遗产。 来源：https://www.youtube.com/watch?v=JzMCwokUTl4