Recursive function causing a stack overflow

Question

I am trying to write a simple sieve function to calculate prime numbers in clojure. I've seen this question about writing an efficient sieve function, but I am not to that point yet. Right now I am just trying to write a very simple (and slow) sieve. Here is what I have come up with:

(defn sieve [potentials primes]
  (if-let [p (first potentials)]
    (recur (filter #(not= (mod % p) 0) potentials) (conj primes p))
    primes))

For small ranges it works fine, but causes a stack overflow for large ranges:

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)

I thought that by using recur this would be a non-stack-consuming looping construct? What am I missing?

Polite

+1 for having stack overflow in the title of your question – Customable

Funny; works for me. What version of Clojure are you using, with what JVM, on what platform? Can you run (range 2 15000) without overflow? – Maryammaryann

Ubuntu 9.10, Java 1.6.0_15, latest snapshot of Clojure 1.2.0 – Polite

Yes, I get an overflow at 15000. Can you run one million without overflowing? – Polite

The title should be "non recursive function causing stack overflow". – Coincidence

Answer 1

You're being hit by filter's laziness. Change (filter ...) to (doall (filter ...)) in your recur form and the problem should go away.

A more in-depth explanation:

The call to filter returns a lazy seq, which materialises actual elements of the filtered seq as required. As written, your code stacks filter upon filter upon filter..., adding one more level of filtering at each iteration; at some point this blows up. The solution is to force the whole result at each iteration so that the next one will do its filtering on a fully realised seq and return a fully realised seq instead of adding an extra layer of lazy seq processing; that's what doall does.

Communist

any thoughts how to find this out? maybe something like macroexpand? – Taluk

Have a look at the stack trace, I'd say. A pile of clojure.lang.LazySeq method calls would be a good indication that the problem is laziness-related. – Coom

Answer 2

Algorithmically the problem is that you continue filtering when there's no more purpose to it. Stopping as early as possible achieves quadratic reduction in recursion depth (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))

Runs OK for 16,000 (performing just 30 iterations instead of 1862), and for 160,000 too, on ideone. Even runs 5% faster without the doall.

Reest