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)

Answer 2

To add to Siddhartha Reddy's answer, you can also borrow the Factorial function form Structure And Interpretation of Computer Programs, with some Clojure-specific tweaks. This gave me pretty good performance even for very large factorial calculations.

(defn fac [n]
  ((fn [product counter max-count]
     (if (> counter max-count)
         product
         (recur (apply *' [counter product])
                (inc counter)
                max-count)))
   1 1 n))

Answer 3

Another, simple recursive implementation simple could be this:

(defn fac [x]
    "Returns the factorial of x"
    (if-not (zero? x) (* x (fac (- x 1))) 1))

Answer 4

Clojure has several ways of busting recursion

explicit tail calls with recur. (they must be truely tail calls so this wont work)

Lazy sequences as mentioned above.

trampolining where you return a function that does the work instead of doing it directly and then call a trampoline function that repeatedly calls its result until it turnes into a real value instead of a function.

(defn fact ([x] (trampoline (fact (dec x) x))) 
           ([x a] (if (<= x 1) a #(fact (dec x) (*' x a)))))
(fact 42)
620448401733239439360000N

memoizing the the case of fact this can really shorten the stack depth, though it is not generally applicable.

ps: I dont have a repl on me so would someone kindly test-fix the trapoline fact function?

Upvotes: 17

Answer 5

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.

Answer 6

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 7

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 8

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 9

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.