clojureで再帰を使用している間にオーバーフローする

Question

私は単純な素数計算を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で試みることなくナイーブ素数をもう一度呼び出すかは、何の違いもないようです。再帰を使用しているときに大きな再帰でエラーが発生するのはなぜですか？

Answer 1

recurは、ループまたは関数ヘッドに繰り返しているかどうかにかかわらず、常に末尾再帰を使用します。問題はremoveへの呼び出しです。 removeは、firstを呼び出して、基本となるseqから要素を取得し、その要素が有効かどうかを確認します。基礎となるseqがremoveへの呼び出しによって作成された場合は、firstをもう一度呼び出します。同じセグメントでremoveを20000回呼び出す場合は、firstを呼び出すにはfirstを20000回呼び出す必要があり、いずれの呼び出しもテール再帰的にすることはできません。したがって、スタックオーバーフローエラー。それはremoveコール（各1が完全にすぐに適用され、具体的な配列ではなく、怠惰な配列を返します）の無限の積み重ねを防ぐため、

、(remove ...)(doall (remove ...))への修正問題を変更します。私はこの方法は、これについて肯定的ではないが、一度に1人の候補者リストを一度にメモリに保持することしかないと思う。そうであれば、それはスペースがあまりにも効率的ではなく、実際にはそれほど遅くはないことを少しのテストで示しています。