Clojure - Eratosthenes的尾递归筛

Question

我在Clojure中实现了Eratosthenes的筛子:

(defn sieve [n]
  (loop [last-tried 2 sift (range 2 (inc n))]
    (if
      (or (nil? last-tried) (> last-tried n))
      sift
      (let [filtered (filter #(or (= % last-tried) (< 0 (rem % last-tried))) sift)]
        (let [next-to-try (first (filter #(> % last-tried) filtered))]
        (recur next-to-try filtered))))))

对于较大的n(如20000),它以堆栈溢出结束.为什么尾部呼叫消除不在这里工作？怎么解决？

Answer 1

问题:进行filter延迟评估,因此每个新级别的过滤都会在调用堆栈上出现.

修复:更改(filter ...)为(doall (filter ...)).

请参阅此处的说明.