Conversion to tail recursion

Question

Hey guys, I'm trying to get cozy with functional programming (particularly with F#), and I've hit a wall when it comes to building tail-recursive functions. I'm pretty good with turning basic recursion (where the function basically calls itself once per invocation), into tail recursion, but I now have a slightly more complicated situation.

In my case, the function must accept a single list as a parameter. When the function is called, I have to remove the first element from the list, and then recur using the remainder of the list. Then I need to apply the first element which I removed in some way to the result of the recursion. Next, I remove the second element and do the same thing (Note: when I say "remove the seond element", that is from the original list, so the list passed at the recursion includes the first element as well). I do the same for the third, fourth, etc. elements of the list.

Is there a way to convert the above situation into a tail-recursive function? Maybe nested tail-recursive functions??? Thank you for any answers.

Okay, so here's my basic code. This particular one is a permutation generator (I'm not too concern with the permutation part, though - it's the recursion I'd like to focusing on):

let permutationsOther str =
  match str with
  | value :: [] ->
    [[value]]
  | _ ->
    let list = (List.map (fun a -> // This applies the remove part for every element a
      let lst = (List.filter (fun b -> b <> a) str) // This part removes element a from the list
      let permutedLst = permutations lst // recursive call
      consToAll a permutedLst // constToAll this is my own function which performs "cons" operation with a and every element in the list permutedLst
    ) str)
    List.reduce (fun acc elem -> elem @ acc) list // flatten list of lists produce by map into a single list

I hope this is clear enough - I'll be happy to provide clarifications if needed.

By the way, I have found just a way to rewrite this particular function so that it only uses a single recursion, but it was a fluke more than an informed decision. However, this has encouraged me that there may be a general method of turning multiple recursion into single recursion, but I have not yet found it.

From what you're describing, your function makes multiple recursive calls, which (IIRC) means you can't convert the code so that it's tail recursive. You'll need to come up with a different recursive formulation to use tail recursion here. — templatetypedef
Oooh - that's what I was afraid of. Maybe I'll find a way to "reinterpret" what I need - maybe recurse then loop through the list - who knows? Thanks for your reply. — Ken Wayne VanderLinde
That's completely wrong. You can turn it into something that's tail recursive for sure. You just have to get creative with the way the function is structured. On the surface you could possibly do the same thing use scanning instead of recursion. Ken, why don't you post your current implementation (or something that resembles it) so we have a play? — OJ.
I'm not quite sure that I got what your function should do. Can you show non tail recursive version as a sample? — desco
Desco, he's asking how to use tail recursion himself, so how can he provide a sample? — OJ.

desco desco · Accepted Answer · 2011-02-19T08:53:38

Conversion to CPS should do the trick:

NOTE 1: Source of the sample is typed directly in browser, so may contain errors :(. But I hope it can demonstrate the general idea.

NOTE 2: consToAll function should be converted to CPS too: consToAll: 'T -> 'T list list -> ('T list list -> 'R) -> 'R

let remove x l = List.filter ((<>) x) l // from original post: should duplicates also be removed ???

let permute l =
    let rec loop k l = 
        match l with
        | [] -> k []
        | [value] -> k [[value]]
        | _ -> filter l [] l (fun r -> r |> List.reduce (fun acc elem -> elem @ acc) |> k )
    and filter l acc orig fk = 
        match l with
        | [] -> fk acc
        | x::xs ->
            remove x orig 
                |> loop (fun res ->
                    consToAll x res (fun rs -> filter xs (rs::acc) orig fk)                    
                    )
    loop id l

Conversion to tail recursion

1 Answers