Clojure：避免埃拉托斯特尼筛中的堆栈溢出？

这是我在 Clojure 中实现的埃拉托斯特尼筛法（基于 SICP 流课程）：

(defn nats-from [n]
  (iterate inc n))

(defn divide? [p q]
  (zero? (rem q p)))

(defn sieve [stream]
  (lazy-seq (cons (first stream)
            (sieve (remove #(divide? (first stream) %) 
               (rest stream))))))

(def primes (sieve (nats-from 2)))

现在，当我取前 100 个素数时，一切都OK了：

(take 100 primes)

但是，如果我尝试采取前 1000 个素数，程序因堆栈溢出而中断。 我想知道是否有可能以某种方式改变函数筛以成为尾递归，并且仍然保留算法的“流”？

有什么帮助吗？？？

首先，这不是埃拉托斯特尼筛......有关详细信息，请参阅我的评论。

其次，对势均力敌的投票表示歉意，因为你的问题并不是我指出的问题的实际重复......我的错。

对正在发生的事情的解释

当然，区别在于您正在尝试构建一个增加的筛子，其中的范围remove调用工作是无限的，因此不可能只包装一个doall周围。解决方案是实施我最近经常链接到的论文中的“真正的”增量 SoE 之一——Melissa E. O'Neill 的论文真正的埃拉托色尼筛子 http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf.

Christophe Grand 编写了这种类型的特别漂亮的 Clojure sieve 实现，并且可以使用here http://clj-me.cgrand.net/2009/07/30/everybody-loves-the-sieve-of-eratosthenes/为了引起所有可能感兴趣的人的钦佩。强烈推荐阅读。

至于问题的根源，我最初认为你的问题是重复的，其中包含对你有用的解释：参见here https://stackoverflow.com/questions/2980587/clojure-tail-recursive-sieve-of-eratosthenes and here https://stackoverflow.com/questions/2946764/recursive-function-causing-a-stack-overflow。再次对仓促结束的投票表示歉意。

为什么尾递归没有帮助

由于问题特别提到将筛选函数尾递归作为可能的解决方案，我想我应该在这里解决这个问题：一般来说，转换惰性序列的函数不应该是尾递归的.

这是需要牢记的非常重要的一点，也是许多没有经验的 Clojure（或 Haskell）程序员会犯的错误。原因是尾递归函数只有在“准备好”时（在计算的最后）才返回其值。 （迭代过程可以在任何特定迭代结束时返回一个值或继续进行下一次迭代。）相比之下，生成惰性序列的函数应该立即返回一个惰性序列对象，该对象封装了一些代码位可以在需要时要求生成序列的头部或尾部。

因此，堆叠惰性转换问题的答案不是使任何内容成为尾递归，而是合并转换。在这种特殊情况下，可以通过使用自定义方案来融合基于优先级队列或映射的过滤操作来获得最佳性能（请参阅上述文章 http://www.cs.hmc.edu/~oneill/papers/Sieve-JFP.pdf了解详情）。