为何OCaml编译器认为我的尾递归函数并非尾递归？

我正在完成OCaml教程中的习题，要求实现计算列表长度的尾递归函数。

非尾递归实现 #

朴素的非尾递归实现代码如下：

let rec length_naive xs  = (** Not tail recursive *)
  match xs with
  | [] -> 0
  | _ :: xs -> 1 + length_naive xs;;

(length_naive [@tailcall]) [1, 2, 3, 4];;

let one_hundred_million = 100000000;;
let non_tail_result = length_naive(List.init one_hundred_million (Fun.id));;
print_endline("Non-tail-recursive result: " ^ string_of_int(non_tail_result));;

编译运行结果符合预期：触发@tailcall警告，执行时因栈溢出失败：

$ ocamlc lib/so.ml
File "lib/so.ml", line 14, characters 0-39:
14 | (length_naive [@tailcall]) [1, 2, 3, 4];;
     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Warning 51 [wrong-tailcall-expectation]: expected tailcall

$ ./a.out
Fatal error: exception Stack_overflow

尾递归实现尝试 #

我的尾递归实现代码如下：

let length xs =
  let rec f xs len =
    match xs with
    | [] -> len
    | _ :: xs -> f xs (len + 1)
  in
  f xs 0;;

(length [@tailcall]) [1, 2, 3, 4];;

let one_hundred_million = 100000000;;
let tail_result = length(List.init one_hundred_million (Fun.id));;
print_endline("Tail recursive result: " ^ string_of_int(tail_result));;

编译运行时：

$ ocamlc lib/so.ml
File "lib/so.ml", line 15, characters 0-33:
15 | (length [@tailcall]) [1, 2, 3, 4];;
     ^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^^
Warning 51 [wrong-tailcall-expectation]: expected tailcall

$ ./a.out
Tail recursive result: 100000000

该函数运行正常未触发栈溢出，但编译器仍警告其并非尾递归。我的疑问是：

1. 若该函数是尾递归，为何编译器会输出警告？
2. 若该函数不是尾递归，为何运行时未出现栈溢出？

使用OCaml编译器版本：4.14.0

问题解答 #

1. 编译器警告的原因 #

你误解了[@tailcall]属性的作用：这个属性是用来标记当前的函数调用是尾调用，而非标记函数本身是尾递归。

在你的代码中，(length [@tailcall]) [1,2,3,4]是给length的调用添加尾调用标记，但length本身不是递归函数——它只是调用了内部的递归函数f。这个标记的位置完全错误：你应该把[@tailcall]加在内部函数f的递归调用处（即f xs (len + 1)这个位置），而非加在外部length函数的调用上。

编译器警告是在提示你：你标记这个调用为尾调用，但它实际上并不是（或者说这个标记没有意义，因为length没有递归调用自身）。

2. 运行时无栈溢出的原因 #

你的length函数内部的嵌套函数f确实是尾递归的：每次递归调用f都是函数的最后一个操作，没有后续计算需要执行，OCaml编译器会将这种尾递归调用优化为循环，不会消耗栈空间。因此当你调用length处理1亿元素的列表时，实际执行的是f的优化后逻辑，自然不会出现栈溢出。

总结：

• 警告与内部递归函数f是否为尾递归无关，完全是因为你错误使用了[@tailcall]属性。
• 运行时无栈溢出是因为内部的f是标准的尾递归，被编译器正确优化了。

内容的提问来源于stack exchange，提问作者kamituel