我（相信）以下函数定义是尾递归的：
fun is_sorted [] = true
| is_sorted [x] = true
| is_sorted (x::(y::xs)) =
if x > y
then false
else is_sorted (y::xs)
简单来说，它等效于以下声明
fun is_sorted [] = true
| is_sorted [x] = true
| is_sorted (x::(y::xs)) =
(x <= y) andalso (is_sorted (y::xs))
但是在此版本中，最后一步是应用“ andalso”，因此它不是尾递归的。或看起来如此，除了（由于NJ的）ML（至少是标准）使用短路评估外，andand实际上是/ not /的最后一步。那么此功能是否可以进行尾部调用优化？还是在其他有趣的情况下，实际上显然不使用尾递归的ML函数得到了优化？
如果我将您的第二个功能转换为OCaml，则会得到以下信息：
let rec is_sorted : int list -> bool = function
| [] -> true
| [_] -> true
| x :: y :: xs -> x < y && is_sorted xs
ocamlopt将其编译为尾递归函数。生成的代码（x86_64）的本质是这样的：
.globl _camlAndalso__is_sorted_1008
_camlAndalso__is_sorted_1008:
.cfi_startproc
.L103:
cmpq $1, %rax
je .L100
movq 8(%rax), %rbx
cmpq $1, %rbx
je .L101
movq (%rbx), %rdi
movq (%rax), %rax
cmpq %rdi, %rax
jge .L102
movq 8(%rbx), %rax
jmp .L103
.align 2
.L102:
movq $1, %rax
ret
.align 2
.L101:
movq $3, %rax
ret
.align 2
.L100:
movq $3, %rax
ret
.cfi_endproc
如您所见，此代码中没有递归调用，只是一个循环。
（但是其他张贴者说的对，OCaml在复杂分析方面所做的工作并不多。这种特殊结果似乎非常简单。）
本文收集自互联网，转载请注明来源。
如有侵权，请联系[email protected] 删除。
我来说两句