Tail recursion in clojure

Question

This is a lisp code that uses tail recursion.

(defun factorial (f n)
    (if (= n 1)
        f
        (factorial (* f n) (- n 1))))

I translate this into clojure code expecting the same tail recursion optimization.

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

However I got this integer overflow (not stack overflow) even with small number such as (fact 1 30).

ArithmeticException integer overflow  clojure.lang.Numbers.throwIntOverflow (Numbers.java:1374)

I tried with recur, but got the same error.

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

What's wrong with the clojure code?

Also it's worth noting that Clojure, because of limitations of the JVM, doesn't support automatic tail call optimization. recur is indeed the way to go for a recursive idiom in this case. — JohnJ
– JohnJ, Commented May 20, 2013 at 18:40
Where in the clojure docs can I find examples of using recur without loop? The way you have used it here. — SultanLegend
– SultanLegend, Commented Jun 9, 2017 at 17:01

A. Webb · Accepted Answer · 2013-05-20 18:22:43Z

18

Nothing, just use BigInts:

(factorial 1N 30N) ;=> 265252859812191058636308480000000N

The arguments may be small, but the result is not!

Note that ticked versions of the arithmetic operators are also available, which support arbitrary precision:

(reduce *' (range 1 31)) ;=> 265252859812191058636308480000000N

answered May 20, 2013 at 18:10

A. Webb

26.5k1 gold badge67 silver badges97 bronze badges

Sign up to request clarification or add additional context in comments.

1 Answer 1