在clojure中使用循環時溢出

我有一個簡單的clojure中的素數計算器（一種低效的算法，但我只是試圖瞭解現在的循環的行爲）。代碼是：在clojure中使用循環時溢出

(defn divisible [x,y] (= 0 (mod x y))) 

(defn naive-primes [primes candidates] 
    (if (seq candidates) 
     (recur (conj primes (first candidates)) 
       (remove (fn [x] (divisible x (first candidates))) candidates)) 
     primes) 
)

只要我不想找到太多的數字，這個工作。例如

(print (sort (naive-primes [] (range 2 2000))))

的作品。對於需要更多遞歸的任何事情，我會遇到溢出錯誤。

(print (sort (naive-primes [] (range 2 20000))))

不起作用。一般來說，無論我是否使用復發或稱爲天真素數而沒有嘗試TCO，似乎都沒有任何區別。爲什麼我在使用重複發生時遇到大型遞歸錯誤？

來源

2012-02-08 DanB

是否需要循環才能獲得尾遞歸？我在你的代碼中看不到循環。我會做出這個答案，但我仍然在學習Clojure。 – octopusgrabbus 2012-02-08 22:42:01

你的代碼適用於Clojure 1.2.1和1.3。我發現唯一的錯誤是當發現質量高達200,000的時候出現'OutOfMemoryError'。 – 2012-02-08 23:02:54

@octopusgrabbus，no，recur也可以以這種方式使用（就在一個函數體內）。請參閱http://clojure.org/special_forms#recur。 – 2012-02-08 23:03:38

recur總是使用尾遞歸，而不管您是否重複循環或函數頭。問題是撥打remove。 remove調用first從底層seq獲取元素，並檢查該元素是否有效。如果底層seq是通過調用remove創建的，則會再次調用first。如果在同一個seq上調用remove 20000次，則調用first需要調用first 20000次，並且這些調用都不能是尾遞歸。因此，堆棧溢出錯誤。

更改(remove ...)到(doall (remove ...))可以解決問題，因爲它可以防止的remove呼叫無限層疊（每一個被完全立即應用，並返回一個混凝土SEQ，而不是一個懶惰SEQ）。我認爲這種方法一次只能保存一個候選人列表，但我對此並不積極。如果是這樣，那麼太空間效率不高，而且一些測試表明它實際上並不太慢。

來源

2012-02-08 23:03:54 Retief

謝謝。如果沒有你的幫助，它會讓我永遠不知所措。儘管doall對我來說似乎有點神奇，但這非常有幫助！ – DanB 2012-02-09 02:46:33

在clojure中使用循環時溢出

回答

相關問題