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

导致堆栈溢出的递归函数

  •  38
  • 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 年前
        1
  •  54
  •   Michał Marczyk    15 年前

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

    更深入的解释:

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

        2
  •  0
  •   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 .