代码之家 › 专栏 › 技术社区 › dbyrne

导致堆栈溢出的递归函数

lazy-sequences lazy-evaluation primes clojure recursion

dbyrne · 技术社区 · 15 年前

我试图写一个简单的筛函数来计算Clojure中的素数。我见过 this 关于编写一个有效的筛选函数的问题,但我还没有到那个程度。现在我只想写一个非常简单(而且很慢)的筛子。我想到的是:

(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 这将是一个非堆栈消耗循环构造?我错过了什么?

2 回复 | 直到 8 年前

MichaÅ Marczyk 15 年前

你被击中了 filter 懒惰。变化 (filter ...) 到 (doall (filter ...)) 在你 recur 形式和问题应该消失。

更深入的解释:

呼唤 滤波器 返回一个惰性序列,该序列根据需要具体化筛选序列的实际元素。正如所写,您的代码堆栈 滤波器 在上面 滤波器 在上面 滤波器 …,再添加一个级别 滤波器 在每一次迭代中;在某一点上这会爆炸。解决方案是在每次迭代时强制整个结果,以便下一个迭代对完全实现的seq进行过滤,并返回完全实现的seq,而不是添加额外的惰性seq处理层;这就是 doall 做。

Will Ness Derri Leahy 8 年前

从算法上来说,问题是当没有更多的目的时,你继续过滤。越早停车,递归深度达到二次约简( sqrt(n) VS n ):

(defn sieve [potentials primes]    
  (if-let [p (first potentials)]
      (if (> (* p p) (last potentials))
        (concat primes potentials)
        (recur (filter (fn [n] (not= (mod n p) 0)) potentials)
               (conj primes p)))
    primes))

可以运行16000次(仅执行30次迭代而不是1862次),也可以运行160000次, on ideone . 即使没有 doall .