导致堆栈溢出的递归函数

Question

我想编写一个简单的筛功能来计算clojure中的素数。我看过this关于编写一个有效的筛选函数的问题，但我还没有到那一点。现在我只是想写一个非常简单（和慢）的筛子。以下是我想出了：

(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的懒惰打中。在您的recur表单中将(filter ...)更改为(doall (filter ...))，问题应该消失。

更深入的解释：

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

Answer 2

算法上，问题在于当没有更多目的时继续过滤。尽早停止实现了递归深度二次还原（sqrt(n)对n）：16000（仅执行30次迭代，而不是1862年）

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

运行正常，并且，为16万太，on ideone。即使没有doall，运行速度也会提高5％。