F# 中的递归函数，它在 n 个类型为 int 的元素的列表中确定两个相邻值中的较大者

Question

我最近开始学习 f#，但我遇到了与主题行中的任务类似的问题。我设法解决了这个任务，但没有使用递归函数。我试图将我的函数转换为递归函数，但它不起作用，因为在函数中我创建了数组，然后我更改了这些元素。请告诉我如何将我的函数转换为递归函数或如何执行此任务。

let list = [8;4;3;3;5;9;-7]
let comp (a,b) = if a>b then a elif b = a then a else b  
let maks (b: _ list)  =
    let x = b.Length
    if x % 2 = 0 then
        let tab = Array.create ((x/2)) 0
        for i = 0 to (x/2)-1 do
            tab.[i] <- (comp(b.Item(2*i),b.Item(2*i+1))) 
        let newlist = tab |> Array.toList 
        newlist
    else
        let tab = Array.create (((x-1)/2)+1) 0
        tab.[(((x-1)/2))] <- b.Item(x-1)
        for i = 0 to ((x-1)/2)-1 do
            tab.[i] <- (comp(b.Item(2*i),b.Item(2*i+1)))
        let newlist = tab |> Array.toList 
        newlist

Answer 1

如果这是一道家庭作业题，我不想放弃答案，所以考虑一下这个伪代码解决方案：

如果列表至少包含两个元素：
- 回答一个新列表，包括：
  - 前两个元素中的较大者，后跟
  - 递归地将函数应用于列表的其余部分
否则列表包含的元素少于两个：
- 回答列表不变

提示：F# 的 pattern matching 功能使其易于实现。

Answer 2

值得注意的是，如果您这样做不是为了学习目的，那么使用 chunkBySize 函数有一个很好的方法：

list 
|> List.chunkBySize 2
|> List.map (fun l -> comp(l.[0], l.[l.Length-1]))

这会将列表分成最多 2 个大小的块。对于每个块，您可以将第一个元素与最后一个元素进行比较，这就是您想要的结果。

Answer 3

感谢您的指导，我成功创建了以下函数：

let rec maks2 (b: _ list,newlist: _ list,i:int) =
let x = b.Length
if x >= 2 then
    if x % 2 = 0 then
        if i < ((x/2)-1)+1 then
            let d = (porownaj(b.Item(2*i),b.Item(2*i+1))) 
            let list2 = d::newlist
            maks2(b,list2,i+1)
        else
        newlist
    else
        if i < ((x/2)-1)+1 then
            let d = (porownaj(b.Item(2*i),b.Item(2*i+1))) 
            let list2 = d::newlist
            maks2(b,list2,i+1)
        else
        let list3 = b.Item(x-1)::newlist
        list3
else
    b

函数运行正常，它接受参数列表、空列表和索引。唯一的问题是返回的列表是颠倒的，即应该在末尾的值在开头。如何将项目添加到列表末尾？

Answer 4

您可以在一个 step.A 典型的递归函数中使用模式匹配来匹配和 check/extract 列表，看起来像：

let rec adjGreater xs =
    match xs with
    | []         -> []
    | [x]        -> [x]
    | x::y::rest -> (if x >= y then x else y) :: adjGreater rest

它检查列表是否为空、有一个元素或有两个元素以及 rest 中的剩余列表。

然后它通过使用 x 或 y 作为第一个元素来构建一个新列表，然后递归地计算剩余的 rest 的结果。

这不是尾递归。尾调用优化版本将是，而不是使用递归调用的结果。您将创建一个新列表，并将到目前为止计算出的值传递给递归函数。通常这样，你想创建一个内部递归循环函数。

由于您只能将值添加到列表的顶部，因此您需要像这样反转递归函数的结果：

let adjGreater xs =
    let rec loop xs result =
        match xs with
        | []         -> result
        | [x]        -> x :: result
        | x::y::rest -> loop rest ((if x >= y then x else y) :: result)
    List.rev (loop xs [])

F# 中的递归函数，它在 n 个类型为 int 的元素的列表中确定两个相邻值中的较大者

Recursive function in F# that determines in a list of n elements of type int, the greater of two adjacent values

f#