recursion - Clojure: Simple factorial causes stack overflow

Question

What am I doing wrong? Simple recursion a few thousand calls deep throws a StackOverflowError.

If the limit of Clojure recursions is so low, how can I rely on it?

(defn fact[x]
  (if (<= x 1) 1 (* x  (fact (- x 1))  )))

user=> (fact 2)
2

user=> (fact 4)
24

user=> (fact 4000)
java.lang.StackOverflowError (NO_SOURCE_FILE:0)

Answer 1

Here's another way:

(defn factorial [n]
  (reduce * (range 1 (inc n))))

This won't blow the stack because range returns a lazy seq, and reduce walks across the seq without holding onto the head.

reduce makes use of chunked seqs if it can, so this can actually perform better than using recur yourself. Using Siddhartha Reddy's recur-based version and this reduce-based version:

user> (time (do (factorial-recur 20000) nil))
"Elapsed time: 2905.910426 msecs"
nil
user> (time (do (factorial-reduce 20000) nil))
"Elapsed time: 2647.277182 msecs"
nil

Just a slight difference. I like to leave my recurring to map and reduce and friends, which are more readable and explicit, and use recur internally a bit more elegantly than I'm likely to do by hand. There are times when you need to recur manually, but not that many in my experience.