转换为尾递归

Question

嘿伙计们,我正在尝试使用函数式编程(特别是使用F#),并且在构建尾递归函数时我遇到了问题.我很好地将基本递归(函数基本上每次调用一次调用自身)转换为尾递归,但我现在有一个稍微复杂的情况.

在我的例子中,该函数必须接受一个列表作为参数.调用该函数时,我必须从列表中删除第一个元素,然后使用列表的其余部分重复.然后我需要将我以某种方式删除的第一个元素应用于递归的结果.接下来,我删除第二个元素并执行相同的操作(注意:当我说"删除seond元素"时,即来自原始列表,因此在递归时传递的列表也包括第一个元素).我对列表的第三,第四等元素也这样做.

有没有办法将上述情况转换为尾递归函数？也许嵌套的尾递归函数??? 谢谢你的任何答案.

---

好的,这是我的基本代码.这个特定的一个是置换生成器(我不太关心置换部分,但是 - 这是我想关注的递归):

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

我希望这很清楚 - 如果需要,我很乐意提供澄清.

顺便说一下,我找到了一种重写这个特定函数的方法,这样它只使用一次递归,但它不仅仅是一个知情决定.但是,这鼓励了我可能有一种将多次递归转换为单次递归的通用方法,但我还没有找到它.

Answer 1

转换为CPS应该可以解决问题:

注1:样本的来源直接在浏览器中输入,因此可能包含错误:(但我希望它可以证明一般的想法.

注2: consToAll函数也应转换为CPS:consToAll:'T - >'T列表 - >('T列表 - >'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