Can an F# function be considered tail recursive it

问题:

Since .net has the TailCall opcode, can this be used to deterime if an F# function is truly tail recursive?

If it is true, has anyone made a VS add-in that identifies tail and non-tail functions?

回答1:

See this blog post on the F# team blog for a summary of how F# compiles tail calls.

In short,

1. Direct recursive tail calls are typically converted into loops.
2. Mutual recursion and indirect non-recursive tail calls are typically turned into .NET tail calls.

but see the full post for all of the gory details.

回答2:

Yes, if the compiler emits the tail call instruction, that call will be tail recursive (as of CLR 4, but there are still some exceptions, where it won't be actually tail recursive). But that doesn't necessarily mean that the whole function is tail recursive. For example, I can imagine QuickSort function compiled so that the first recursive call is not tail recursive and the second one is.

Also, just because some function does not contain the tail instruction, it doesn't necessarily mean that it is not tail recursive. The JIT compiler can recognize a tail call even without the tail instruction and optimize it as such.

What's more, the F# compiler sometimes compiles recursive functions in a non-recursive way. This is somewhat different than normal tail call optimization and the tail instruction is not used, but the overall effect is similar.