递归函数导致堆栈溢出

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返回一个惰性序列，该序列将根据需要具体化已过滤序列的实际元素。如所写，您的代码会在...的filter基础filter上堆叠filter，filter在每次迭代时再增加一层ing；在某个时候，它炸毁了。解决方案是在每次迭代时强制执行整个结果，以便下一个迭代将对完全实现的seq进行过滤，并返回完全实现的seq，而不是添加额外的惰性seq处理层。就是doall这样。