Clojure - Eratosthenes 的尾递归筛法 [英] Clojure - tail recursive sieve of Eratosthenes

问题描述

我在 Clojure 中实现了 Eratosthenes 筛法:

I have this implementation of the sieve of Eratosthenes in Clojure:

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

For larger n (like 20000) it ends with stack overflow. Why doesn't tail call elimination work here? How to fix it?

推荐答案

问题:filter 执行惰性求值，因此每个新级别的过滤都在调用堆栈上徘徊.

Problem: filter does lazy evaluation, so each new level of filtering hangs around on the call stack.

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

Fix: Change (filter ...) to (doall (filter ...)).

在此处查看说明.

这篇关于Clojure - Eratosthenes 的尾递归筛法的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！