CODEWITHSUNDEEP
recursionf#f#-interactive
Alexander
Alexander

Reputation: 119

Tail recursion in mutually recursive functions

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

Upvotes: 5

Views: 1116

Answers (2)

Mulan
Mulan

Reputation: 135197

I second the observation that your attempt definitely does not put the recursion in tail position

How I would handle moving the recursion into tail position would be using a continuation. To do so, we'd have to implement fk and gk variants which have a continuation parameter, then f and g can be implemented using fk and gk respectively

I'm not an F# expert, but I can illustrate this quite simply with JavaScript. I wouldn't ordinarily post an answer using a different language, but since the syntax is so similar, I think it will be helpful to you. It also has the added benefit that you can run this answer in the browser to see it working

// f helper
let fk = (n, k) => {
  if (n < 10)
    return gk(n + 1, g => k("f" + g))
  else
    return k("f")
}
    
// g helper
let gk = (n, k) => {
  if (n < 10)
    return fk(n + 1, f => k("g" + f))
  else
    return k("g")
}
    
let f = n =>
  fk(n, x => x)

let g = n =>
  gk(n, x => x)
  
console.log(f(0))  // fgfgfgfgfgf
console.log(g(0))  // gfgfgfgfgfg
console.log(f(5))  // fgfgfg
console.log(g(5))  // gfgfgf
console.log(f(11)) // f
console.log(g(11)) // g

Upvotes: 2

Fyodor Soikin
Fyodor Soikin

Reputation: 80724

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.

Upvotes: 6

Related Questions