Rfactor这个F＃代码到尾递归

Question

我写了一些代码来学习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个素数？

Answer 1

关于你的问题的第一部分，如果你想要写一个递归列表建筑功能tail-递归地，您应该将中间结果列表作为函数的一个额外参数传递。在你的情况，这将是像

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）。当你达到你的结局条件，只需吐出累计结果。我在另一个函数中包含了尾递归辅助函数，所以函数签名保持不变。

正如您所看到的，对aux的呼叫是n <> 1情况下发生的唯一呼叫，因此也是最后一个呼叫。它现在是尾递归的，并将编译成一个while循环。

我已经定好了你的版本和我的版本，生成了2000个素数。我的版本速度提高了16％，但仍然非常慢。为了产生素数，我喜欢使用命令式阵列筛。功能不是很好，但非常（非常）快。

Answer 2

为什么不干脆写：

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 

Answer 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 

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

Answer 4

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

我描述了一个快速任意大小的埃拉托色尼的筛在F＃here是累积的成果转化为不断增长的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) 

Answer 5

我知道这是有点晚了，答案是已经接受。但是，我相信一个好的一步一步的指导，可以让OP或任何其他人对此感兴趣。这里有一些技巧肯定帮了我。因为，正如其他人所说，我将使用除素数之外的一个横跨前沿的例子，因为有更好的方法来产生素数。

考虑一个计数函数的简单实现，该函数将创建一个从一些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'实际上并没有倒计时。这是在n > 0时继续建立的方式的神器，然后在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 []