Question on mutual recursion

Learning
1

While writing some convoluted function on a custom recursive type, I ended up with the following pattern:

let rec f n =
  if n < 0 then n else
    let g n = f (n - 1) in
    g (n - 1)

which I figure has the same behavior as the mutual recursion


let rec f n =
  if n < 0 then n else
    g (n - 1)
and g n = f (n - 1)

What are the differences of these two (knowing that I do not care about g being available for later) ? For instance, in terms of performance, allocation. Is it different if the calls to f and g are not tail-calls ? In the first case, a non-recursive function g is “created” for each call to f, so it may be worse for allocation ? But maybe mutual recursion is worse ?

2

Actually, no closure is created for g because its free variables (namely, f) are global, hence constant. So there isn’t any allocation at all. The code generated in both cases is pretty much the same, except that the compiler more readily inlines the first g because it is not exposed outside f.

Incidentally, you can compare the generated code for each case by passing -dlambda to the compiler (for the Lambda intermediate form, used for bytecode generation) and/or -dcmm (for the C-- intermediate form, used for native code generation).

Cheers,
Nicolas

2 Likes