導致堆棧溢出的遞歸函數

我想編寫一個簡單的篩功能來計算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這將是一個非 - 堆棧消耗循環結構？我錯過了什麼？

來源

2010-06-01 dbyrne

+12

+1在您的問題的標題中出現堆棧溢出 – radman 2010-06-01 01:12:36

有趣;爲我工作。你在什麼平臺上使用什麼版本的Clojure，以及哪些JVM？你可以運行'（範圍2 15000）'沒有溢出嗎？ – 2010-06-01 01:17:55

Ubuntu 9.10，Java 1.6.0_15，Clojure的最新快照1.2.0 – dbyrne 2010-06-01 01:30:12

你被filter的懶惰打中。在您的recur表單中將(filter ...)更改爲(doall (filter ...))，問題應該消失。

更深入的解釋：

到filter調用返回一個懶惰SEQ，根據需要，其物化過濾的SEQ的實際的元件。正如所寫的，你的代碼在filter上filter ... filter ...，在每次迭代時增加一個級別的filter;在某個時候，這會爆炸。解決方法是在每次迭代時強制整個結果，以便下一個將在完全實現的seq上進行過濾並返回完全實現的seq，而不是添加額外的lazy seq處理層;這就是doall所做的。

來源

2010-06-01 01:34:59

謝謝！這解決了我的問題。優秀的解釋。 – dbyrne 2010-06-01 01:44:51

任何想法如何找到這個？也許像macroexpand？ – edbond 2010-06-05 20:29:20

看看堆棧跟蹤，我會說。一堆'clojure.lang.LazySeq'方法調用將很好地表明問題與懶惰有關。 – 2010-06-05 22:23:38

算法上，問題在於當沒有更多目的時繼續過濾。儘早停止實現了遞歸深度二次還原（sqrt(n)對n）：16000（僅執行30次迭代，而不是1862年）

(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))

運行正常，並且，爲16萬太，on ideone。即使沒有doall，運行速度也會提高5％。

來源

2017-01-12 19:06:49

導致堆棧溢出的遞歸函數

回答

相關問題