尾调用与尾调用优化

尾调用 & 尾递归

假设函数 A 调用了函数 B，我们称函数 A 为 Caller，函数 B 为 Callee。

尾调用（Tail-call）指的是：Caller 最后只需要返回 Callee 这个函数调用的计算结果，其他运算都执行完成了¹

如果 Callee 就是 Caller 自己，即出现了尾调用 + 递归调用的情况，那么这个函数就符合尾递归（Tail-recursive）的特点，暂且称其为尾递归函数

尾调用优化（TCO）

根据函数调用的原理，本来函数 A 调用函数 B 的时候，我们需要为函数 B 创建一个 stack frame，然后压入到函数调用栈中，后续需要根据 stack frame 里面的函数返回地址进行返回。但如果这是一个尾调用，我们何必多此一举呢？反正函数 A 已经执行了它所有的计算过程，只需要等待尾调用的函数 B 的返回结果并将其返回即可

尾调用优化（Tail-call Optimization，TCO）的思想就是这样的：如果是尾调用，就不创建新的 stack frame，而是复用 Caller 的 stack frame 就好了 ²

那么，尾调用优化的好处是什么呢？显然，尾递归函数的时间开销和空间开销大大降低了，我们可以放心地随意用尾递归而不会用担心栈溢出的问题，只要对应的编程语言支持尾调用优化并开启即可

将普通递归函数改写为尾递归函数

但并不是所有的递归函数都是尾递归函数，因此，我们还需要知道如何将任意一个递归函数改写为尾递归函数，一个比较流行的方式是 Accumulator 模式

具体步骤如下 ³

• 创建一个辅助函数 helper，一般而言它会有 2 个参数
  • 当前正在处理的数据
  • 当前已经“累计的值”
• 辅助函数 helper 的 base case 变为：返回最后“累计的值”
• 原本递归函数的 base case 变为：调用辅助函数 helper

用经典的求解阶乘程序为例，首先用 dune 创建一个项目

$ dune init project tco

然后在 ./tco/bin/main.ml 里面写下求阶乘的递归函数

let rec factorial n =
  match n with
    0 | 1 -> 1 
  | n -> n * factorial (n - 1)

显然，它不是一个尾递归函数，这是因为：我们计算完 factorial (n - 1) 的时候，还需要把它乘以 n 才能返回，所以，它并不符合最后只需要返回函数调用的结果这个要求

现在我们将这个函数改写为尾递归函数

let factorial_tco n =
  let rec helper cur acc =
    match cur with
    | 0 | 1 -> acc (* 返回“计算出来的值” *)
    | cur -> (helper [@tailcall]) (cur - 1) (acc * cur)
  in
  helper n 1  (* 调用辅助函数 *)

为了测试 2 个不同的实现的性能差异，我们可以用 core_bench 工具。首先，先安装必要的库

$ opam install core_bench

接下来修改配置文件，将 ./tco/bin/dune 修改为

(executable
 (public_name tco)
 (name main)
 (libraries tco core core_bench core_unix.command_unix))

然后增加关于性能测试的代码，最后 ./tco/bin/main.ml 文件长下面这样

open Core
open Core_bench

let rec factorial n =
  match n with
  | 0 | 1 -> 1
  | n -> n * factorial (n - 1)

let factorial_tco n =
  let rec helper cur acc =
    match cur with
    | 0 | 1 -> acc
    | cur -> (helper [@tailcall]) (cur - 1) (acc * cur)
  in
  helper n 1

(* Benchmark *)
let bench () =
  Bench.make_command
    [
      Bench.Test.create ~name:"factorial" (fun () -> factorial 10000);
      Bench.Test.create ~name:"factorial_tco" (fun () -> factorial_tco 10000);
    ]
  |> Command_unix.run

let _ = bench ()

接下来构建项目并执行即可

$ dune build
$ dune exec tco

在我的 MacBook M3 Air 上的输出结果如下所示

Estimated testing time 20s (2 benchmarks x 10s). Change using '-quota'.
┌───────────────┬──────────┬────────────┐
│ Name          │ Time/Run │ Percentage │
├───────────────┼──────────┼────────────┤
│ factorial     │  40.42us │    100.00% │
│ factorial_tco │  10.06us │     24.90% │
└───────────────┴──────────┴────────────┘

可以看到，开启尾调用优化的递归函数的时间开销是原来的 1/4 而已🚀

总结

以上就是关于「尾调用」&「尾调用优化」的全部内容，说白了，尾调用优化就是将计算的结果暂时存储在函数的参数里面，从而避免了不断创建 stack frame 的开销。性能上是提升了但是代码也不那么优美了。所以，建议还是正常写递归函数，当出现性能瓶颈的时候再改写为尾递归函数~

参考