Clojure: Simple factorial causes stack overflow

Question

What am i doing wrong? Simple recursion of few thousand deep throws "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

Factorial numbers are by their nature very big. I'm not sure how Clojure deals with this (but I do see it works with java), but any implementation that does not use big numbers will overflow very fast.

Edit: This is without taking into consideration the fact that you are using recursion for this, which is also likely to use up resources.

Edit x2: If the implementation is using big numbers, which, as far as I know, are usually arrays, coupled with recursion (one big number copy per function entry, always saved on the stack due to the function calls) would explain a stack overflow. Try doing it in a for loop to see if that is the problem.

Answer 2

Use recur instead of the recursive function call (since the JVM does not support tail call optimisation). Something like:

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

Answer 3

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.

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)

Answer 4

How about keeping a map of previous results? After calculating (fact 20), it store the result, so when you call (fact 21), it is a much quicker operation.

This would help with limiting the number of function calls, but not the size of the answer. How large of a value can you pass (fact) before it overflows?

Answer 5

The stack depth is a small annoyance (yet configurable), but even in a language with tail recursion like Scheme or F# you'd eventually run out of stack space with your code.

As far as I can tell, your code is unlikely to be tail recursion optimized even in an environment that supports tail recursion transparently. You would want to look at a continuation-passing style to minimize stack depth.

Here's a canonical example in Scheme from Wikipedia, which could be translated to Clojure, F# or another functional language without much trouble:

(define factorial
  (lambda (n)
      (let fact ([i n] [acc 1])
        (if (zero? i)
            acc
            (fact (- i 1) (* acc i))))))

Answer 6

As l0st3d suggested, consider using recur or lazy-seq.

Also, try to make your sequence lazy by building it using the built-in sequence forms as a opposed to doing it directly.

Here's an example of using the built-in sequence forms to create a lazy Fibonacci sequence (from the Programming Clojure book):

(defn fibo []
  (map first (iterate (fn [[a b]] [b (+ a b)]) [0 1])))

=> (take 5 (fibo))
(0 1 1 2 3)

Answer 7

As I was about to post the following, I see that it's almost the same as the Scheme example posted by JasonTrue... Anyway, here's an implementation in Clojure:

user=> (defn fact[x]
        ((fn [n so_far]
          (if (<= n 1)
              so_far
              (recur (dec n) (* so_far n)))) x 1))
#'user/fact
user=> (fact 0)
1
user=> (fact 1)
1
user=> (fact 2)
2
user=> (fact 3)
6
user=> (fact 4)
24
user=> (fact 5)
120

etc.

Answer 8

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.