在日常业务开发中，习惯命令式编程范式的程序员可能对尾调用优化并不熟悉，甚至也对递归操作敬而远之。但对于 Haskell 这种完全 pure 的函数式语言，想要实现迭代的效果，唯一的办法是递归。
从数学角度看，递归是唯一选项，它的表达性很强，通过它我们能用简洁的公式表达复杂的数学意图。回忆一下，我们的数学教科书中，从高等数学到实变函数与泛函分析，你都找不到一个命令式的循环表达（while、loop、for）。一切都似乎很完美，然而，受限于当前人类对图灵机的硅基实现，在有限的内存中无限制地递归会使程序过早 stack overflow，以至于 panic。
本文将从一个案例开始，尝试让读者感知数学、函数式编程到命令式编程的联系。然后我们一起看看工业界中成熟的编程语言 Scala 如何进行尾调用优化。最后，以一个稍微复杂的案例引导读者思考。

案例 - Factorial 乘积

对于一个正整数，阶乘（factorial）是所有小于及等于该数的正整数的积，并且0的阶乘为1。自然数n的阶乘写作n!。亦即 n! = 1 × 2 × 3 × … × (n-1) × n。
阶乘 n! 的公式对于人类而言足够清晰，然而对于计算机，尝试理解三个点的省略号 … 并不容易。因此，我们也更进一步地以递归方式定义：0! = 1，n! = n × (n -1)! (n ∈ N+)。（幸好乘法运算符合交换律）
现在，工作交给程序员，我们用 Scala 代码实现递归方式的阶乘：

  1. def factorial(n: Int) : Int = if n == 0 then 1 else n * factorial(n - 1)

公式 31 个字符，代码 72 个字符，但代码的可读性甚至比公式还高，证明 Scala 表达相当优秀。
我们使用 SICP 的方式模拟程序运行，比如输入 n=5：
factorial(5) = 5 factorial(4)
factorial(5) = 5 4 factorial(3)
factorial(5) = 5 4 3 factorial(2)
factorial(5) = 5 4 3 2 factorial(1)
factorial(5) = 5 4 3 2 1 factorial(0)
factorial(5) = 5 4 3 2 1 1
factorial(5) = 5 4 3 2 1
factorial(5) = 5 4 3 2
factorial(5) = 5 4 6
factorial(5) = 5 24
factorial(5) = 120
直观来看，5、4、3 这些较大的数字更早驻留在栈中，直至较小的数字算出来后，他们才能参与运算。但正如前面所说，内存是有限的，因此计算机的 stack 不能无限扩张。笔者的工作平台 JVM 默认 -xss256k，如果输入的 n 不加限制，很容易抛出 StackOverflowException。

尾调用优化

现在我们做一个尾调用处理，就是把程序改写一下，使得所有 return 的地方只有一个值，或者调用：

  1. def factorial(n: Int, acc: Int = 1) : Int = {
  2.   if n == 0 then acc
  3.   else factorial(n - 1, n * acc)
  4. }

代码有了，老规矩，模拟一下运行过程：
factorial(5, 1) = factorial(4, 5)
factorial(4, 5) = factorial(3, 20)
factorial(3, 20) = factorial(2, 60)
factorial(2, 60) = factorial(1, 120)
factorial(1, 120) = factorial(0, 120)
factorial(0, 120) = 120
factorial(1, 120) = 120
factorial(2, 60) = 120
factorial(3, 20) = 120
factorial(4, 5) = 120
factorial(5, 1) = 120
这时候可能有读者发现问题了，从上往下数还是11层，这尾调用的意义何在呢？这时候就需要编译器帮忙了。scalac 发现这个函数所有的 return 都是尾调用，于是在它做了点优化，只使用一个栈帧就完成了计算。比如 factorial(5, 1) 调用了 factorial(4, 5)，但由于调用的时候，函数体内已经没有其它变量了，所以 factorial(5, 1) 这个栈帧可以放心地释放掉。同理，最后计算 factorial(0, 120) = 120，前面的栈帧早就释放掉了，至始至终只有一个栈帧在内存中。（多少有点过河拆桥的意思）

Scala 尾调用优化

如果到这一步还有好奇的读者想知道 Scala 怎么个过河拆桥，我们可以通过 Scala 调试模式看看：

scalac -Xprint:all Fact.scala

  1. def fact(n: Int, acc: Int): Int = {
  2.     var acc$tailLocal1: Int = acc
  3.     var n$tailLocal1: Int = n
  4.     while <empty> do
  5.       tailLabel1[Unit]:
  6.         return
  7.          {
  8.            if n$tailLocal1.<=(1) then acc$tailLocal1 else
  9.              {
  10.                 val n$tailLocal1$tmp1: Int = n$tailLocal1.-(1)
  11.                 val acc$tailLocal1$tmp1: Int = n$tailLocal1.*(acc$tailLocal1)
  12.                 n$tailLocal1 = n$tailLocal1$tmp1
  13.                 acc$tailLocal1 = acc$tailLocal1$tmp1
  14.              }
  15.          }
  16. }

Scala 规定入参是不可变的，因此 n 和 acc 进入函数体后会被赋值给两个本地变量，接下来就是个 loop 循环（参考 Rust 语法，社区认为 while ture 是 evil 的），循环体内就是 n 的 -1 步长，并且使用 acc 累积结果。
太多的 var 可能不容易看明白，换一下变量名就容易理解了：

  1. def fact(n: Int): Int = {
  2.   var acc = 1
  3.   for i <- n to 1 by -1 do acc *= i
  4.   acc
  5. }

可以发现，Scala 的尾调用优化本质上就是将递归代码改写为我们熟悉的迭代。到这一步，尾调用优化已经很清晰了。但对于 Scala，稍加改造还能简约代码：

  1. def fact(n: Int): Int = (1 to n).reduce(_ * _)
  3. def fact(n: Int): Int = (1 to n).product

先看第一行，通过 1 to n 生成一个 [1, n] 的闭合集合，然后通过 reduce 把序列的元素相乘。到这已经足够精简，但 Scala 完备的 List 操作甚至提供了 product，相比之下，Java 只有 sum。这为 Scala 刷算法提供了极大的便利，连 python3 都望尘莫及。

案例 - Fibonacci 斐波那契数列

接下来看一个稍复杂的案例，斐波那契数列。数学公式：F(0)=0，F(1)=1, F(n) = F(n - 1) + F(n - 2)（n ≥ 2，n ∈ N*）。如果使用 Scala 实现：

  1. def fibonacci(n: Int) : Int = {
  2.   if n <= 2 then 1
  3.   else fibonacci(n - 1) * fibonacci(n - 2)
  4. }

实现起来很自然，并且到了两个 return 已经没有本地变量，似乎是尾调用？答案是否定的，在调用 fibonacci(n - 1) 之后，我们还不能释放栈帧，因为 fibonacci(n - 2) 还没计算。
进行了尾调用优化的递归方法，称为尾递归，这种 return 调用两次以上自身的递归，称为树状递归。在 Fibonacci 的案例中，需要参与到下一次迭代的变量有两个，其中 fibonacci(n - 1) 可以定义为 acc0，另外 fibonacci(n - 2) 定义为 acc1，接下来按照尾调用的定义，尝试改写一下：

  1. @tailrec
  2. def fib(n: Int, f0: Int = 0, f1: Int = 1): Int = {
  3.   if n > 2 then fib(n - 1, f1, f1 + f0) else acc1
  4. }

上一个案例 Factorial 在 return 只调用了一次自身，这属于线性递归，较为容易改造，但 Fibonacci 是树状递归，不容易直接改写为尾调用。有没有方法论可以帮助改写尾调用呢？答案是有，先来看第一种。

迭代形式转换

  1. def fib(n: Int): Int = {
  2.   var f0 = 0
  3.   var f1 = 1
  4.   if n < 2 then return n
  5.   for _ <- 2 to n do
  6.     val tmp = f0
  7.     f0 = f1
  8.     f1 = f1 + tmp
  9.   f1
  10. }

先写出迭代形式的实现，然后对号入座转换为尾递归实现。到这儿可能要质疑，既然都已经写出迭代实现了，那为什么不直接用迭代实现呢，毕竟 Scala 编译器最终还是会把尾递归优化为迭代？
一个显而易见的好处是代码精简，尾递归形式函数体只有一行，没有任何本地变量，不用提前返回，甚至不用考虑迭代边界。这符合函数式编程的提倡，一个函数实现只有一行，并且只有一处 return。

CPS变换

Continuation Passing Style 是一种编程形式。通过 CPS变换，可以把任意递归函数改写成尾调用形式，以continuation链的形式，将递归占用的栈空间转移到堆上，避免爆栈的悲剧。
但需要注意的是，该方法并不能降低算法的时间复杂度，因此本文不作进一步介绍，读者可以根据参考文献扩展。

参考文献