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?
In order to prevent stack overflow bugs, you must have a base case where the function stops make new recursive calls. If there is no base case then the function calls will never stop and eventually a stack overflow will occur. Here is an example of a recursive function with a base case.
There is no general number of recursions that will cause stack overflow. Removing the variable 'neighbour' will allow for the function to recur further as each recursion takes less memory, but it will still eventually cause stack overflow.
Recursive functions use something called “the call stack.” When a program calls a function, that function goes on top of the call stack. This is similar to a stack of books. You add things one at a time. Then, when you are ready to take something off, you always take off the top item.
lang. StackOverflowError indicates that the application stack is exhausted and is usually caused by deep or infinite recursion.
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 filter
ing 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.
If you love us? You can donate to us via Paypal or buy me a coffee so we can maintain and grow! Thank you!
Donate Us With