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

The stack size, I understand, depends on the JVM you are using as well as the platform. If you are using the Sun JVM, you can use the -Xss and -XThreadStackSize parameters to set the stack size.

The preferred way to do recursion in Clojure though is to use loop/recur:

(defn fact [x]
    (loop [n x f 1]
        (if (= n 1)
            f
            (recur (dec n) (* f n)))))

Clojure will do tail-call optimization for this; that ensures that you’ll never run into StackOverflowErrors.

And due defn implies a loop binding, you could omit the loop expression, and use its arguments as the function argument. And to make it a 1 argument function, use the multiary caracteristic of functions:

(defn fact
  ([n] (fact n 1))
  ([n f]
  (if (<= n 1)
    f
    (recur (dec n) (* f n)))))

Edit: For the record, here is a Clojure function that returns a lazy sequence of all the factorials:

(defn factorials []
    (letfn [(factorial-seq [n fact]
                           (lazy-seq
                             (cons fact (factorial-seq (inc n) (* (inc n) fact)))))]
      (factorial-seq 1 1)))

(take 5 (factorials)) ; will return (1 2 6 24 120)