用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

基本上逻辑是这样的。对于基本情况，如果列表是空的，那么你就完成了。只需返回空列表。对于包含头部项目（x）和尾部（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 

Answer 2

我不知道这是否编译，因为我只是写它在SO。另外，这当然不是最好的方法，但它可以让你在递归轨道（迈克z显示更好的方式）。

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

实质上，它由几个步骤组成。

首先是拉动头从名单中（如果它是一个空的列表，然后返回一个空列表）

二是随e比较头

三是发送列表的尾部向下递归

的线

第四被重建的列表中，任选地包括所述列表的头部。

List.Filter函数只是一个通用函数，它允许您注入一个函数来替换第二步并为您节省所有样板。通常你想在所有情况下使用List.Filter，除了在学习它的时候。