用F#递归思考

Question

我有一个函数,它接受一个int和一个int列表.它返回一个小于第一个参数的int列表.

我想要复制相同的代码而不使用List.Filter:

let less e L = 
   L |> List.filter(fun a -> a < e)

less 3 [1;2;4;5]

我想学习递归思考,好像我是用SML编写的

我怎么递归写这个？

Answer 1

基本上逻辑是这样的.对于基本情况,如果列表为空,那么您就完成了.只需返回空列表.对于在head(x)和tail(xs)处具有项目的列表,如果x < e返回x附加less应用于尾部的结果.否则,只需返回less应用于尾部.

let rec less e L =
  match L with
  | [] -> []
  | x :: xs -> if x < e then x :: (less e xs) else (less e xs)

但是,这有点效率低,因为它不是尾递归的.尾递归调用是指立即返回递归调用的结果.这些更有效,因为编译器可以将它们基本上转换为不会为每次递归消耗额外堆栈空间的循环.为此,我们需要一个带累加器的辅助函数:

let lessTailRec e L =
  let rec loop e L acc =
    match L with
    | [] -> acc
    | x :: xs -> if x < e then loop e xs (x :: acc) else loop e xs acc
  loop e L [] |> List.rev