为什么这个函数不是尾递归的？

Question

我写了一个基本的 Eratosthenes 筛选函数，最初以 head::(innerSieve tail) 结尾，我注意到它不是递归的。

然后我修改如下，使用累加器。这段代码现在应该是尾递归的：

let Sieve n =     

    let rec innerSieve primes numbers =     
        match numbers with
        | [] -> primes
        | h :: t -> innerSieve (h :: primes) (List.filter (fun x -> x % h > 0) t) 

    innerSieve [] [2 .. n] |> List.rev

printf "%A" (Sieve 10000)

然而，即使在发布模式下，此函数的内存使用量仍以 n 的大小以极快的速度增长（每 +1000 +1-2MB ).我错过了什么吗？

编辑：VS 运行的屏幕截图，其中 n = 100M：

Answer 1

关于你的问题：函数是 尾递归 - 这并不意味着它具有神奇的记忆效率。

你的真正的问题是List在内存中handled/kept的方式（它们变得非常大，非常快。

这就是列表的问题：如果它们变大（开销很大...），它们并不是真正的最佳选择，所以通常的第一步是改为使用数组。

是的，它在这里工作正常（内存方面）：

let inline divides d n = n % d > 0

let rec innerSieve primes numbers =     
    if Array.isEmpty numbers
    then primes
    else 
        let h = numbers.[0]
        let numbers' = numbers |> Array.filter (divides h)
        in innerSieve (h :: primes) numbers'

let Sieve n =     
    innerSieve [] [| 2 .. n |] |> List.rev

当然这也会运行 很长一段时间 ...但是在我的机器上内存消耗小于 200MB 所以 IMO 还不错（...当然，我的机器仍在思考，并且会思考一段时间，所以可能我只是再次终止进程并结束它 - 你可以让它运行代替 ;)).

顺便说一句：将其切换为 seq 而不是 list 可能是一个有趣的练习，这样您就可以看到素数一个接一个地弹出……可能会让等待时间更愉快

为什么这个函数不是尾递归的？

Why isn't this function tail recursive?

f#

tail-recursion