Tail recursion in mutually recursive functions

Question

I have the following code:

let rec f n =
    if n < 10 then "f" + g (n+1) else "f"
and g n =
    if n < 10 then "g" + f (n+1) else "g"

I want to make these mutually recursive functions tail recursive for optimization. I have tried the following :

let rec fT n = 
    let rec loop a = 
        if n < 10 then "f" + gT (a) else "f"
    loop (n + 1) 
and gT n =
    let rec loop a = 
        if n < 10 then "g" + fT (a) else "g"
    loop (n + 1) 

Is that a correct tail recursive version? If no, a hint in the right direction would be greatly appreciated.

EDIT (Second take on a solution):

let rec fA n = 
    let rec loop n a = 
        if n < 10 then loop (n + 1) ("f" + a) else a
    loop n "f"
and gA n =
    let rec loop n a = 
        if n < 10 then loop (n + 1) ("g" + a) else a
    loop n "g"

EDIT (Third take on a solution):

let rec fA n a = 
    if n < 10 then gA (n + 1) (a + "f") else a
and gA n a =
    if n < 10 then fA (n + 1) (a + "g") else a

EDIT (The correct solution):

let rec fA n a = 
    if n < 10 then gA (n + 1) (a + "f") else (a + "f")
and gA n a =
    if n < 10 then fA (n + 1) (a + "g") else (a + "g")

Answer 1

Your solution is most definitely not tail-recursive.

"Tail-recursion" is such recursion where every recursive call is the last thing that the function does. This concept is important, because it means that the runtime can opt out of keeping a stack frame between the calls: since the recursive call is the very last thing, and the calling function doesn't need to do anything else after that, the runtime can skip returning control to the calling function, and have the called function return right to the top-level caller. This allows for expressing recursive algorithms of arbitrary depth without fear of running out of stack space.

In your implementation, however, the function fT.loop calls function gT, and then prepends "f" to whatever gT returned. This prepending of "f" happens after gT has returned, and therefore the call to gT is not the last thing that fT.loop does. Ergo, it is not tail-recursive.

In order to convert "regular" recursion into the "tail" kind, you have to "turn the logic inside out", so to speak. Let's look at the function f: it calls g and then prepends "f" to whatever g returned. This "f" prefix is the whole "contribution" of function f in the total computation. Now, if we want tail recursion, it means we can't make the "contribution" after the recursive call. This means that the contribution has to happen before. But if we do the contribution before the call and don't do anything after, then how do we avoid losing that contribution? The only way is to pass the contribution into the recursive call as argument.

This is the general idea behind tail-recursive computation: instead of waiting for the nested call to complete and then adding something to the output, we do the adding first and pass what has been "added so far" into the recursive call.

Going back to your specific example: since the contribution of f is the "f" character, it needs to add this character to what has been computed "so far" and pass that into the recursive call, which will then do the same, and so on. The "so far" argument should have the semantics of "compute whatever you were going to compute, and then prepend my 'so far' to that".

Since you've only asked for a "hint", and this is obviously homework (forgive me if I'm wrong), I am not going to post the actual code. Let me know if you'd rather I did.