Overflow when using recur in clojure

Question

I have a simple clojure prime calculator (inefficient algorithm, but I'm just trying to understand recur behavior at the moment). The code:

(defn divisible [x,y] (= 0 (mod xy))) (defn naive-primes [primes candidates] (if (seq candidates) (recur (conj primes (first candidates)) (remove (fn [x] (divisible x (first candidates))) candidates)) primes) ) 

This works until I try to find too many numbers. for example

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

working. For something requiring more recursion, I get an overflow error.

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

will not work. In general, I use recur or call naive numbers again without trying TCO, it seems to make no difference. Why am I getting errors for large recursions when using recur?

Answer 1

recur always uses tail recursion, whether you are repeating in a loop or in the head of a function. The problem is with remove calls. remove calls first to get the element from base seq and checks to see if that element is valid. If the base seq was created by the remove call, you will get another first call. If you call remove 20,000 times on the same seq, calling first requires calling first 20,000 times, and none of the calls can be tail recursive. Therefore, a mistake.

Changing (remove ...) to (doall (remove ...)) fixes the problem, as it prevents endlessly stacking remove calls (each one is fully applied immediately and returns a specific seq, not lazy seq). I think this method only ever stores one list of candidates in memory at a time, although I'm not sure about that. If so, it is not too inefficient, and a little testing shows that in reality it is not much slower.