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)

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

Solution 2

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.

Solution 3

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?

Solution 4

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.

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

View more solutions