2

我写了一些代码来学习 F#。这是一个例子：

let nextPrime list=
    let rec loop n=
        match n with
        | _ when (list |> List.filter (fun x -> x <= ( n |> double |> sqrt |> int)) |> List.forall (fun x -> n % x <> 0)) -> n
        | _ -> loop (n+1)
    loop (List.max list + 1)

let rec findPrimes num=
    match num with
    | 1 -> [2]
    | n -> 
        let temp = findPrimes <| n-1
        (nextPrime temp ) :: temp

//find 10 primes
findPrimes 10 |> printfn "%A"

我很高兴它可以正常工作！

我完全是递归的初学者

递归是一件美妙的事情。

我认为findPrimes效率不高。

如果可能的话，有人帮我将 findPrimes 重构为尾递归吗？

顺便说一句，有没有更有效的方法来找到前 n 个素数？

4

5 回答 5

4

关于你问题的第一部分，如果你想写一个递归列表构建函数尾部递归，你应该将中间结果列表作为额外参数传递给函数。在您的情况下，这将类似于

let findPrimesTailRecursive num =
    let rec aux acc num = 
        match num with
        | 1 -> acc
        | n -> aux ((nextPrime acc)::acc) (n-1)
    aux [2] num

递归函数 aux 将其结果收集在一个方便地称为 acc 的额外参数中（如 acc-umulator 中）。当你达到你的结束条件时，只需吐出累积的结果。我已将尾递归辅助函数包装在另一个函数中，因此函数签名保持不变。

如您所见，在 n <> 1 情况下，对 aux 的调用是唯一的，因此也是最后一个调用。它现在是尾递归的，将编译成一个 while 循环。

我已经为你的版本和我的版本计时，生成了 2000 个素数。我的版本快了 16%，但还是很慢。为了生成素数，我喜欢使用命令式数组筛。不是很实用，但非常（非常）快。

于 2010-06-04T11:33:37.687 回答
3

为什么不简单地写：

let isPrime n =
    if n<=1 then false
    else
        let m = int(sqrt (float(n)))
        {2..m} |> Seq.forall (fun i->n%i<>0)

let findPrimes n = 
    {2..n} |> Seq.filter isPrime |> Seq.toList

或筛子（非常快）：

let generatePrimes max=
    let p = Array.create (max+1) true
    let rec filter i step = 
        if i <= max then 
            p.[i] <- false
            filter (i+step) step
    {2..int (sqrt (float max))} |> Seq.iter (fun i->filter (i+i) i) 
    {2..max} |> Seq.filter (fun i->p.[i]) |> Seq.toArray
于 2010-06-04T10:52:12.433 回答
3

另一种方法是使用额外的延续参数来使 findPrimes 尾递归。这种技术总是有效的。它将避免堆栈溢出，但可能不会使您的代码更快。

另外，我将您的 nextPrime 函数与我使用的样式更接近。

let nextPrime list=
    let rec loop n = if list |> List.filter (fun x -> x*x <= n) 
                             |> List.forall (fun x -> n % x <> 0) 
                     then n
                     else loop (n+1)
    loop (1 + List.head list)

let rec findPrimesC num cont =
        match num with
        | 1 -> cont [2]
        | n -> findPrimesC (n-1) (fun temp -> nextPrime temp :: temp |> cont)

let findPrimes num = findPrimesC num (fun res -> res)        
findPrimes 10

正如其他人所说，有更快的方法来生成素数。

于 2010-06-04T11:46:31.113 回答
2

我知道这有点晚了，答案已经被接受了。但是，我相信 OP 或其他任何人可能对制作尾递归的良好分步指南感兴趣。这里有一些肯定对我有帮助的提示。我将使用除素数生成之外的一个直截了当的示例，因为正如其他人所说，有更好的方法来生成素数。

考虑一个简单的 count 函数实现，它将创建一个从 some 向下计数的整数列表n。此版本不是尾递归，因此对于长列表，您将遇到堆栈溢出异常：

let rec countDown = function
  | 0 -> []
  | n -> n :: countDown (n - 1)
(*         ^
           |... the cons operator is in the tail position
                as such it is evaluated last.  this drags
                stack frames through subsequent recursive
                calls *)

解决此问题的一种方法是使用参数化函数应用延续传递样式：

let countDown' n =
  let rec countDown n k =
    match n with
    | 0 -> k [] (*            v--- this is continuation passing style *)
    | n -> countDown (n - 1) (fun ns -> n :: k ns)
(*          ^
            |... the recursive call is now in tail position *)
  countDown n (fun ns -> ns) 
(*              ^
                |... and we initialize k with the identity function *)

然后，将此参数化函数重构为专门的表示。请注意，该功能countDown'实际上并没有倒计时。这是在 when 建立延续n > 0然后在 when 求值的方式的产物n = 0。如果您有类似第一个示例的内容，并且无法弄清楚如何使其尾递归，那么我建议您编写第二个示例，然后尝试对其进行优化以消除函数参数k。这肯定会提高可读性。这是对第二个示例的优化：

let countDown'' n =
  let rec countDown n ns =
    match n with
    | 0 -> List.rev ns  (* reverse so we are actually counting down again *)
    | n -> countDown (n - 1) (n :: ns)
  countDown n []
于 2012-01-25T20:11:44.893 回答
2

顺便说一句，有没有更有效的方法来找到前 n 个素数？

我在这里用 F# 描述了一个快速的任意大小的 Eratosthenes 筛子，它将其结果累积成一个不断增长的ResizeArray:

> let primes =
    let a = ResizeArray[2]
    let grow() =
      let p0 = a.[a.Count-1]+1
      let b = Array.create p0 true
      for di in a do
        let rec loop i =
          if i<b.Length then
            b.[i] <- false
            loop(i+di)
        let i0 = p0/di*di
        loop(if i0<p0 then i0+di-p0 else i0-p0)
      for i=0 to b.Length-1 do
        if b.[i] then a.Add(p0+i)
    fun n ->
      while n >= a.Count do
        grow()
      a.[n];;
val primes : (int -> int)
于 2010-06-04T19:20:23.597 回答