# Clojure’s Tail Recursion Feature

Lisp-based languages, like mathematical processing, relies on
recursion. The quintessential example, discussed ad nauseum, is the
**factorial** function, which is often rendered *as it’s definition*:

(defun factorial (n) (if (< n 2) 1 (* n (factorial (- n 1))))) (factorial 5) ;; Returns 120

The problem with this approach is large calculations may “blow” the stack. Some systems, catch the exception and move the entire world over to heap.

The traditional solution is to use tail recursion. If the last operation in a function is a recursive call to that function, then it is easy for the language to treat the operation as a loop.

(defun factorial (n) (defun inner-factorial (cnt acc) (if (< cnt 2) acc (inner-factorial (- cnt 1) (* acc cnt)))) (inner-factorial n 1))

Notice the hallmarks of this approach:

- An inner function that does the work
- An accumulator that holds the current calculation
- The accumulator is returned when the break-out condition is reach.

While Clojure is a Lisp-based language, it also runs on top of a host virtual machine (usually the JVM), and currently the JVM does not support tail recursion.

The solution was to create the `loop`

/ `recur`

construct. Here is a
rendering of the previous code in Clojure:

(defn factorial [n] (loop [cnt n acc 1] (if (< cnt 2) acc (recur (dec cnt) (* cnt acc)))))

At first, I didn’t care much for the special consideration for dealing
with tail recursion that *just happens* in other Lisp languages,
however, I’ve changed my mind for the following reasons:

First, we often have to have an accumulator which we hide inside an
inner function or lambda, the `loop`

simply replaces what we normally
do anyway.

Second, while you may want tail recursion, you may not be sure you are
getting tail recursion. The Clojure approach ensures that `recur`

is
the last call in the function, and throws an error if not.

What appeared to me to be a kludge at first, has become a feature to me.