返回资讯中心
外部精选
软件工程
#开发者实时流

尾调用优化原理解析:递归为何不必耗尽调用栈

来源标题:Tail-Call Optimization Explained: Why Recursion Doesn't Have to Blow Your Stack

尾调用优化(TCO)是一种编译器技术,让递归函数复用当前栈帧而非新建栈帧,从而支持任意深度的递归而不耗尽栈空间。文章以 Java 递归 Fibonacci 触发 StackOverflowError 为例,解释了函数调用时栈帧的压栈与弹出过程。部分语言已支持 TCO 数十年,Java 则长期争论是否引入。

Hacker News 最新andsoitis2026/11/9 · 8 天前30 分钟阅读

以下正文由 AI 翻译自 Hacker News 最新(原文版权归原站所有),可能存在偏差,重要内容请以原文为准。

大学时我第一次遇到 StackOverflowError。当时我在用 Java 写一个递归的斐波那契函数,输入小的时候一切正常。后来我试着算 fib(50000),JVM 直接挂了。那是我第一次听说尾调用优化,说实话,我很难相信居然不是每种语言都有这玩意儿。

尾调用优化(TCO)就是这样一种特性:一旦你弄懂了它,就会纳闷为什么它不是到处都有。有些语言几十年前就有了。另一些语言,比如 Java,也同样争论了几十年。下面我来拆解一下它是什么、怎么工作,以及你到底能在哪里用上它。

尾调用优化是一种编译器技术,它改写递归函数,让函数复用当前的栈帧,而不是创建新的栈帧。结果呢?你可以递归到任意深度,永远不用担心栈空间耗尽。

要理解这件事为什么重要,你得先明白一个函数调用自身时发生了什么。

每次调用函数,运行时都会在调用栈上压入一个新帧。这个帧保存着函数的局部变量、参数和返回地址。函数返回时,它的帧被弹出。

在递归中,每一次递归调用都会再加一个帧。如果你在计算 factorial(10000),那就是一万个栈帧同时待在内存里。大多数运行时给栈分配的空间在 512KB 到 1MB 之间。递归得足够深,你就完蛋了。

下面是一个没有 TCO 的经典 Clojure 阶乘:

(defn factorial [n] (if (zero? n) 1N (* n (factorial (dec n))))) Copy 调用 (factorial 6),看栈是怎么长的:

(factorial 6) (* 6 (factorial 5)) (* 6 (* 5 (factorial 4))) (* 6 (* 5 (* 4 (factorial 3)))) (* 6 (* 5 (* 4 (* 3 (factorial 2))))) (* 6 (* 5 (* 4 (* 3 (* 2 (factorial 1)))))) (* 6 (* 5 (* 4 (* 3 (* 2 (* 1 (factorial 0))))))) Copy 一次乘法都还没发生,就已经堆了 7 个帧。每个帧都得等下面那个帧返回。对于 factorial(100000),你需要十万个帧。你的栈撑不住。

诀窍在于重新组织递归,让递归调用成为函数做的最后一件事。它后面没有乘法。没有进一步的计算。只有递归调用,别的什么都没有。

下面是 Clojure 中的尾递归版本:

(defn factorial ([n] (factorial n 1N)) ([n acc] (if (zero? n) acc (recur (dec n) (* acc n))))) Copy 关键区别在于:我们不再等递归调用返回后再做乘法,而是把累计结果作为累加器参数传进去。乘法发生在递归调用之前,而不是之后。

现在栈的样子完全不同了:

(factorial 6 1) (factorial 5 6) ;; reused frame (factorial 4 30) ;; reused frame (factorial 3 120) ;; reused frame (factorial 2 360) ;; reused frame (factorial 1 720) ;; reused frame (factorial 0 720) ;; reused frame => 720 Copy 一个帧。每次复用。编译器看到递归调用之后什么都没发生,于是它直接用新的参数跳回函数开头。底层其实就是一个 while 循环。

并不是所有语言都以同样的方式对待 TCO。有些自动做,有些给你工具让你主动选择,还有些……干脆不做。

这些语言不需要你要求,就会优化尾调用:

Scheme 和 Racket 就是围绕 TCO 构建的。Scheme 规范(R5RS 及之后的版本)实际上要求实现支持正规的尾调用。这不是可选项。这也是为什么 Scheme 是计算机科学课程中教授递归的首选语言。

(define (factorial n acc) (if (= n 0) acc (factorial (- n 1) (* acc n)))) (factorial 1000000 1) ;; works fine, no stack overflow Copy Erlang 和 Elixir 也自动做 TCO。在 BEAM 虚拟机(两者都跑在它上面)中,尾递归函数是写循环的标准方式。Elixir 里没有 for 或 while 循环。一切都是递归,而 TCO 让它能跑起来。

defmodule Math do def factorial(0, acc), do: acc def factorial(n, acc), do: factorial(n - 1, n * acc) end Math.factorial(1_000_000, 1) # runs in constant stack space Copy Haskell 支持 TCO,但因为惰性求值而变得棘手。在 Haskell 中,尾调用可能会堆积未求值的 thunk(延迟计算),而不是实际的值。有时你需要用 seq 或 bang patterns 强制严格求值,才能获得完整的好处。

OCaml 干净利落地处理 TCO。编译器会自动把尾递归函数变成循环。OCaml 的模式匹配和函数式风格让尾递归感觉很自然。

Scala 给你 @tailrec 注解。它并不启用 TCO。它告诉编译器去验证你的函数确实是尾递归的,如果不是就抛出编译错误。Scala 编译器本来就会在可能的时候优化尾调用,但 @tailrec 给你一个保证。

import scala.annotation.tailrec def factorial(n: BigInt, acc: BigInt = 1): BigInt = { if (n <= 1) acc else factorial(n - 1, n * acc) factorial(100000) // works perfectly Copy 如果你不小心用 @tailrec 写了非尾递归的代码,编译器会告诉你:

error: could not optimize @tailrec annotated method factorial: it contains a recursive call not in tail position Copy 这真的很有用。你在编译期就抓住了问题,而不是等到生产环境应用崩溃时才发现。

Clojure 用 recur 采取了不同的方法。JVM 原生不支持 TCO,所以 Clojure 没法透明地优化尾调用。取而代之的是,recur 显式地告诉编译器「跳回这个函数的开头」。如果你试图在非尾位置使用 recur,就会得到编译错误。

(defn factorial [n] (loop [i n acc 1N] (if (zero? i) acc (recur (dec i) (* acc i))))) Copy Rich Hickey(Clojure 的创造者)把这一点作为有意识的设计选择。他希望开发者清楚自己什么时候在依赖尾调用行为,而不是想当然地认为编译器会处理它。

(原文较长,此处译出前 6000 字,完整内容请点「打开原文」。)

正文由 探How 从来源站点 RSS 同步,内容未经改写;遇到排版缺失或需要图片、视频时请以原文为准。

打开原文
去社区讨论 →