递归函数导致堆栈溢出

Question

我正在尝试编写一个简单的筛子函数来计算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 ...))您的recur形式,问题就会消失.

更深入的解释:

调用filter返回一个惰性seq,它根据需要实现过滤seq的实际元素.由于写的,你的代码堆filter在filter后filter......,加入一个多层次filter荷兰国际集团在每次迭代; 在某些时候,这会爆发.解决方案是在每次迭代时强制执行整个结果,以便下一个将在完全实现的seq上进行过滤并返回完全实现的seq,而不是添加额外的lazy seq处理层; 这是什么doall.