# Understand Clojure recur and tail recursion optimization

### The simple recursion

Or naive recursion, linear recursion, mundane recursion. They are semantically equivalent to iteration. But recursive version consumes more memory. At each loop, recursive function call creates a new stack frame and all the local variables have a new copy , by doing this, the recursive version don't have to mutate anything, the cost is stack frame consumption.

When the loop count increase in simple recursion, the stack is doomed to explosion. This makes the simple recursion almost useless in practice.

The simple recursion causes a stack overflow.

user=> (defn fact [n] (if (= n 1) 1 (*' n (fact (- n 1 ))) ) ) (fact 4) #'user/fact user=> user=> 24 user=> (fact 60000) StackOverflowError user/fact (NO_SOURCE_FILE:44) user=>

Notice here we are using *', this is a auto-promoting math function, which will cast Integer(or Long) to BigInt. If we use * , we will get ArithmeticException integer overflow instead a stack overflow error.

### Tail recursion

A recursion call as the last statement of a function is said to be a tail recursion. But example above is not, the fact recursive call is not the last statment but and add function.

A simple tail recursion will look like this

(defn recurseme [n] (if (= n 0) () (do (println (str n "th loop")) (recurseme (- n 1)) ) ) )

The problem of tail recursion is, after the calling, the stack frame of current call will never be accessed. So keep it is an obvious wasting of resources. And its easy to eliminate them by executing a goto statment and reusing the current stack frame.

See more about tail recursion

### Auto tail recursion optimization

If the compiler smart enough, it can identify tail recursion and optimize it automatically. Such as Scheme which provided generalized tail call optimization. But this is not default for all languages and compilers. Gereally, tail recursive optimization in functional language is much more necessary than imperative language. Because in imperative language, use iteration is more nature than tail recursion.

### JVM and tail recursion optimization

The JVM which Clojure is built on, does not support tail recursive optimization. Its not designed to functional language after all. This becomes a problem when trying to implement functional language on JVM, becuase for a functional language, tail recursion is a thing can be omitted. For example scala and clojure used different approach on this problem.

### Clojure's recur special form

Now we can discuss about Clojure's recur special form. Put is simply , recur in Clojure is an explicit way of tail recursion optimization. We can compare to scala which do tail recursion optimization in compiler.

For scala, compiler will identify which recursion call can be optimized and do it for you. But Clojure takes a different approach, Clojure will not implicitly optimize tail recursion, you have to use recur special form to explicitly represent this is a tail recursion. The code will be transformed to a loop which will not consume stack.

For our example , the factorial function is not a tail recursion, because after recursion call returned, the result need to multiply with n, we can convert it to a tail recursion and optimize it with recur special form. See tail recursion to find how its trasformed.

(defn fact [n] (loop [current n acc 1] (if (= 1 current) acc (recur (- current 1) (*' acc current)) ) ) ) (fact 6000) (fact 4)

So why Clojure make it explicit? Lets first see what kind of problem may arise when compiler do optimization implicitly. The problem is you can not tell whether compiler will optimize as you wished. Because determine whether a recursion call is a real tail recursion may be tricky. As the factorial example, someone may incorrectly think its a tail recursion, but its not, and compiler will not optimize it which is not you wanted. There will be no warnings, the compile just don't do the optimization and gives you an unefficient code.

For Clojure, if its not a tail recursion and you used recur, it report an error. Suppose we have a function like this

(defn recurseme [n] (if (= n 0) () (do (println (str n "th loop")) (recurseme (- n 1)) ) ) )

Whic just simulate a loop that looping n times and at each loop print a message. This is a tail recursion. So we can optimize simply by doing this.

(defn recurseme [n] (if (= n 0) () (do (println (str n "th loop")) (recur (- n 1)) ) ) )

But this one is not a tail recursion.

(defn recurseme [n] (println (if (= n 0) () (do (println (str n "th loop")) (recurseme (- n 1)) ) ) ) )

Clojure report this error

CompilerException java.lang.UnsupportedOperationException: Can only recur from tail position, compiling:(NO_SOURCE_PATH:60:8)

Now you can check your code and find out whats wrong with the recursive call and make optimizable.

# Clojure

## Clojure Internals