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这将是一个非堆栈消耗循环结构? 我错过了什么?

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

更深入的解释:

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

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%,也没有问题。

Interesting Posts