recursion函数导致堆栈溢出

我正在尝试编写一个简单的筛选函数来计算clojure中的素数。 我已经看到了关于编写一个有效的筛选函数的问题，但我还没有到那个时候。 现在我只是想写一个非常简单的（慢）筛。 这是我所想到的：

(defn sieve [potentials primes] (if-let [p (first potentials)] (recur (filter #(not= (mod % p) 0) potentials) (conj primes p)) primes)) 

对于小范围，它工作正常，但会导致大范围堆栈溢出：

 user=> (sieve (range 2 30) []) [2 3 5 7 11 13 17 19 23 29] user=> (sieve (range 2 15000) []) java.lang.StackOverflowError (NO_SOURCE_FILE:0) 

我认为，通过使用recur这将是一个非堆栈消耗循环结构？ 我错过了什么？

Answer 1

你被filter的懒惰打了。 更改(filter ...)到(doall (filter ...))在您的recurforms和问题应该消失。

更深入的解释：

filter的调用返回一个懒惰的seq，根据需要实现被过滤的seq的实际元素。 正如所写的，你的代码栈在filter上filter …，在每次迭代中增加一个filter级别; 在某个时候，这个爆炸。 解决scheme是在每次迭代时强制整个结果，以便下一个将在完全实现的seq上进行过滤，并返回一个完全实现的seq，而不是添加额外的lazy seq处理层; 这就是doall所做的。

Answer 2

algorithm上，问题是当没有更多的目的时继续过滤。 尽可能早地实现recursion深度的二次减less（ sqrt(n)与n ）：

 (defn sieve [potentials primes] (if-let [p (first potentials)] (if (> (* pp) (last potentials)) (concat primes potentials) (recur (filter (fn [n] (not= (mod np) 0)) potentials) (conj primes p))) primes)) 

可以运行16,000（只执行30次而不是1862），也可以在ideone上运行 16万次 。 即使运行速度提高了5％，也没有问题。