一尘不染

Clojure-Eratosthenes的尾递归筛

algorithm

我在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),它以堆栈溢出结束。为什么尾音消除在这里不起作用?如何解决?


阅读 470

收藏
2020-07-28

共1个答案

一尘不染

问题:进行filter惰性评估,因此每个新级别的过滤都会在调用堆栈上徘徊。

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

2020-07-28