Conversion to tail recursion

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.

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