如何使用尾递归

我只是寻找一个小小的建议重写代码，如何使用尾递归如何使用尾递归

open Core.Std;; 

let rec dig x = 
    match x with 
    | 0 -> [] 
    | _ -> x :: dig (x - 1) 
;; 


let() = 
    let numbers = dig 10 in 
    List.iter ~f:(Printf.printf "%d, ") numbers; 
    Printf.printf "\n"; 
;;

重写代码的任何建议，将有助于

来源

2015-09-15 grigoriytretyakov

let dig x = 
    let rec f x s = 
     match x with 
     | 0 -> s 
     | _ -> f (x-1) (x::s) 
    f x []

这是你想要的吗？它使用尾递归。

编辑：对于seq递减，只需将（x :: s）替换为（List.append s [x]）或（s @ [x]），但这不是一个好主意，List.rev是好：

let dig x = 
    let rec f x s = 
     match x with 
     | 0 -> s 
     | _ -> f (x-1) (s @ [x]) 
    f x []

来源

2015-09-15 15:52:08 Syeerzy

这不完全是我要找的。您的功能会增加顺序，但我正在尝试创建递减顺序。 – grigoriytretyakov

你应该用'List.rev'来取消结果以保持顺序 – ivg

let dig x = 
    let rec f s z = 
    if z = x then s 
    else f (z::s) (z+1) 
    in 
    f [] 0

不知道这是否你的船浮筒：您可能需要调整取决于边界的情况下，如果你想为0或包含起始编号。

来源

2015-09-15 19:18:07 lambdapower

好了，它似乎可以有多种解决方案

open Core.Std;; 


let rec digtail ?(l=[]) x = 
    match x with 
    | 0 -> l 
    | _ -> digtail ~l: (l @ [x]) (x - 1) 
;; 


let() = 
    let numbers = digtail 10 in 
    List.iter ~f:(Printf.printf "%d, ") numbers; 
    Printf.printf "\n"; 
;;

感谢所有，你帮了不少忙。

来源

2015-09-16 09:52:11 grigoriytretyakov

'l @ [x]'使得你的函数是二次的而不是线性的：对于每次调用，你遍历到目前为止建立的整个'l'一个单一的元素。另外'@'本身并不是尾递归，因此实际上你将问题从'digtail'转换为'@'。你真的应该更喜欢Syeerzi的解决方案（最后一个'List.rev'由ivg提出） – Virgile

如果你不想向后建筑名单（这在我看来是完全没有问题），也不符合0而不是n开始你的递归后使用List.rev，你可以使用某种延续：

let dig2 x = 
    let rec aux x kont = 
    match x with 
    | 0 -> kont 
    | _ -> aux (x-1) (fun l -> kont (x::l)) 
in 
aux x (fun l -> l) [];;

基本上每个步骤都会返回一个函数，给定由其余步骤构建的列表，它将为其添加x。我们用身份函数开始递归，因为我们还没有任何东西需要构建。然后，当我们退出递归时，我们只需要将空列表应用到获得的函数中。

来源

2015-09-16 13:50:54 Virgile

你知道，这不是我不喜欢使用List.rev或内部递归函数的解决方案，我只是想找到解决这个问题的更多方法简单的任务。我只开始学习OCaml，并希望看到其他人如何在简单任务中使用它。（关于我的英语学习，我可以说同样的话）。 – grigoriytretyakov

这对我很好。我只是想强调，前两个答案比我更习惯，这确实只是为了完整。 – Virgile

“你可以使用某种延续”也称为“差异列表”。 – gallais

如何使用尾递归

回答

相关问题