CODEWITHSUNDEEP
haskellf#functional-programmingmlmutual-recursion
ruben2020
ruben2020

Reputation: 1549

Mutually recursive functions in functional programming languages

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?

Upvotes: 0

Views: 1031

Answers (2)

Andreas Rossberg
Andreas Rossberg

Reputation: 36098

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).

Upvotes: 5

dfeuer
dfeuer

Reputation: 48591

Since F# is in the ML family, I imagine this is a fairly simple matter: plain let just isn't recursive at all, and mutually recursive functions need to be bound together by a let rec. This does simplify the compiler's analysis to a certain extent. In Haskell, the compiler ends up breaking up the code into similar blocks itself, both to support type inference and to perform optimizations. The ML way is arguably more predictable. I don't think either approach is inherently better.

You mention lazy evaluation, and I suspect that does help swing the balance to some extent in each language. In ML, a recursively defined value pretty much has to be a function, whereas in Haskell, any type of value can be defined recursively.

Upvotes: 1

Related Questions