代码之家 › 专栏 › 技术社区 › kev

r将此F#代码转换为尾部递归

tail-recursion f#

kev · 技术社区 · 16 年前

我写了一些代码来学习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"

我很高兴它能起作用!

我是个初学者递归

递归是一件美妙的事情。

查找时间 效率不高。

有人帮我重构FindTime 尾部递归 如果可能的话?

顺便问一下,有没有更有效的方法 ?

5 回复 | 直到 10 年前

cfern 16 年前

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)。当你达到你的最终状态时,把累积的结果吐出来。我已经在另一个函数中包装了tail recursive helper函数,因此函数签名保持不变。

我给你和我的版本计时,生成2000个素数。我的版本快了16%,但仍然相当慢。为了生成素数,我喜欢使用命令式数组。不是很实用,但是很快。

RD1 16 年前

另一种方法是使用额外的continuation参数使findprimestail递归。这种技术总是有效的。它将避免堆栈溢出,但可能不会使代码更快。

另外,我把你的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

Yin Zhu 16 年前

为什么不干脆写:

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

J D 16 年前

顺便问一下,有没有更有效的方法来找到前n个素数?

我描述了一个快速的任意大小的埃拉托斯烯筛# 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)

ninegrid 12 年前

考虑一下count函数的一个简单实现,它将创建一个整数列表,从某个整数开始倒计时 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 []