Many others are wiser than I am about OCaml internals, but for simple functions it's pretty easy to see tail recursion in the generated assembly code of ocamlopt:
$ cat tailrec.ml
let rec f a x = if x <= 1 then a else f (a * x) (x - 1)
let rec g x = if x <= 1 then 1 else x * g (x - 1)
$ ocamlopt -c -S tailrec.ml
If you ignore a lot of extra output you see this for f
:
_camlTailrec__f_1008:
.cfi_startproc
.L101:
cmpq $3, %rbx
jg .L100
ret
.align 2
.L100:
movq %rbx, %rdi
addq $-2, %rdi
sarq $1, %rbx
decq %rax
imulq %rbx, %rax
incq %rax
movq %rdi, %rbx
jmp .L101
.cfi_endproc
The compiler has changed the recursive call into a loop (i.e., the function is tail recursive).
Here's what you get for g
:
.cfi_startproc
subq $8, %rsp
.cfi_adjust_cfa_offset 8
.L103:
cmpq $3, %rax
jg .L102
movq $3, %rax
addq $8, %rsp
.cfi_adjust_cfa_offset -8
ret
.cfi_adjust_cfa_offset 8
.align 2
.L102:
movq %rax, 0(%rsp)
addq $-2, %rax
call _camlTailrec__g_1011
.L104:
movq %rax, %rbx
sarq $1, %rbx
movq 0(%rsp), %rax
decq %rax
imulq %rbx, %rax
incq %rax
addq $8, %rsp
.cfi_adjust_cfa_offset -8
ret
.cfi_adjust_cfa_offset 8
.cfi_endproc
The recursion is handled by an actual recursive call (not tail recursive).
As I say, there may be better ways to figure this out if you understand the OCaml intermediate forms better than I do.