9

I have a simple prime number calculator in clojure (an inefficient algorithm, but I'm just trying to understand the behavior of recur for now). The code is:

(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)
)

This works as long as I am not trying to find too many numbers. For example 

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

works. For anything requiring more recursion, I get an overflow error. 

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

will not work. In general, whether I use recur or call naive-primes again without the attempt at TCO doesn't appear to make any difference. Why am I getting errors for large recursions while using recur?

DanB
  • 3,755
  • 4
  • 22
  • 22
  • Does recur require loop to get tail recursion? I don't see loop in your code. I'd make this an answer, but I'm still learning Clojure. – octopusgrabbus Feb 08 '12 at 22:42
  • Your code works for me in Clojure 1.2.1 and 1.3. The only error I eventually get is an `OutOfMemoryError` when finding primes up to 200,000. – Jon Gauthier Feb 08 '12 at 23:02
  • @octopusgrabbus, no, recur can be used in this fashion (just within a function body) as well. See http://clojure.org/special_forms#recur. – Jon Gauthier Feb 08 '12 at 23:03
  • @HansEngel running at the repl in 1.3, I get a stack overflow error when finding primes up to 200,000. Explanation below. – Retief Feb 08 '12 at 23:05
  • 1
    My apologies for not finding this before posting. My question was similar to http://stackoverflow.com/questions/2946764/recursive-function-causing-a-stack-overflow – DanB Feb 09 '12 at 05:20
  • Why don't you use the anonymous function literal and write something like: `(remove (#(divisible % (first candidates))) candidates)`? – viebel Feb 09 '12 at 06:27
  • @Yehonathan, Is that going to help with the memory issue, or is it just a stylistic suggestion? – DanB Feb 10 '12 at 00:27
  • stylistic only. But style is essential in clojure. – viebel Feb 10 '12 at 06:30
  • why `sort` though? aren't the primes created already in order? --- I've added an algorithm-improving answer at the earlier question btw, that doesn't need the `doall` (will vote to close this one as a duplicate, as this is what it is :) ). – Will Ness Jan 13 '17 at 11:46
  • Possible duplicate of [Recursive function causing a stack overflow](http://stackoverflow.com/questions/2946764/recursive-function-causing-a-stack-overflow) – Will Ness Jan 13 '17 at 11:46

1 Answers1

18

recur always uses tail recursion, regardless of whether you are recurring to a loop or a function head. The issue is the calls to remove. remove calls first to get the element from the underlying seq and checks to see if that element is valid. If the underlying seq was created by a call to remove, you get another call to first. If you call remove 20000 times on the same seq, calling first requires calling first 20000 times, and none of the calls can be tail recursive. Hence, the stack overflow error.

Changing (remove ...) to (doall (remove ...)) fixes the problem, since it prevents the infinite stacking of remove calls (each one gets fully applied immediately and returns a concrete seq, not a lazy seq). I think this method only ever keeps one candidates list in memory at one time, though I am not positive about this. If so, it isn't too space inefficient, and a bit of testing shows that it isn't actually much slower.

Retief
  • 3,199
  • 17
  • 16
  • Thanks. It would have taken me forever to figure that out without your help. Even though doall seems a little magical to me, this was extremely helpful! – DanB Feb 09 '12 at 02:46