A single recursive function can have tail recursion optimization applied to it, to prevent stack overflow, but what about mutually recursive functions?
This answer shows how to define mutually recursive functions in F#:
let rec F() =
G()
and G() =
F()
Is it defined in this way, so that the generated native machine code or bytecode will consist ultimately of only one function with tail recursion optimization applied to both F and G? Will this prevent stack overflow?
How does the algorithm for tail call work, for mutually recursive functions?
On the other hand, Haskell does not need such a syntax. Is it because of Haskell's lazy evaluation? Or as @augustss suggests, are Haskell compilers also doing the same as above?
Functional languages usually do so-called proper tail call optimisation, which is completely independent of recursion. Any tail call is optimised into a jump, be it a recursive call, a call to a previously defined function, a partially applied function, or even a call to a first-class function. For example:
g x = let y = 2*x in abs x -- tail call
add x = (+) x -- tail call
apply f x = f x -- tail call
F# should be able to do all that, since the CLR has a tail call instruction (even though it has been known to be slow).