为什么编译器认为这个函数是非尾递归的？

Question

我正在解决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

现在是我尝试编写尾递归版本的时候了：

$ 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

编译并运行它：

$ 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

所以它有效，堆栈溢出异常没有被抛出。但是，编译器会警告该函数不是尾递归的。我的问题是：

• 如果这个函数是尾递归的，为什么编译器会打印警告？
• 如果这个函数不是尾递归，为什么呢？

我正在使用 OCaml 编译器 v 4.14.0。

Answer 1

尾递归函数和尾调用可优化（函数）调用是两个不同的概念。Beingtail-call是函数调用的属性，而beingtail-recursive是函数的属性。

在你的例子中

length []

是对尾递归函数的不可尾部调用优化的调用。

定义中的函数调用是可length尾部调用优化的：

  let rec f xs len =
    match xs with
    | [] -> len
    | _ :: xs -> (f[@tailcall]) xs (len + 1)

更明确地说，

• 当可以重用当前堆栈帧从而避免分配新的堆栈帧时，函数调用是尾部调用可优化的。特别是，如果可以快捷返回地址，则在递归函数定义内对递归函数的调用可能会重用父调用堆栈。

• f当函数体中对函数的所有调用都是尾调用可优化时，该函数就是尾递归的。