Why is this stack overflow instead of using tail recursion?

Question

I have defined the following functions in Clojure.

; return the input unchanged (defn same [x] x) ; Recursively call the function on the input N times (defn recurse-n-times [input function n] (if (= n 0) input (recurse-n-times (function input) function (- n 1)) ) ) 

Here are some of the results of my recursive function:

 (recurse-n-times 0 inc 5) ; returns 5, as expected (recurse-n-times 0 same 5) ; returns 0, as expected (recurse-n-times 0 same 5000) ; StackOverflowError: ; clojure.lang.Numbers$LongOps.combine ; (Numbers.java:394) 

I do not understand why I received a StackOverflowError . The last thing recurse-n-times does is call, so I expect it to use tail recursion and not expand the stack at all.

I will expect this alternative definition to give a StackOverflowError :

 (defn bad-recurse-n-times [input function n] (if (= n 0) input (function (alt-recurse-n-times input function (- n 1))) ) ) 

Why recurse-n-times n't recurse-n-times use tail recursion?

Answer 1

This is a limitation of the JVM, not Clojure. JVM does not support TCO.

Clojure offers a special form for this recur

 (defn recurse-n-times [input function n] (if (= n 0) input (recur (function input) function (- n 1)))) (recurse-n-times 0 same 500000) ;; will work 

The recur form should appear in the tail position, otherwise the Clojure compiler will complain about it.

Note that recur is the only non-stack loop construct in Clojure. There is no tail call optimization, and using self-start to loop unknown boundaries is not recommended. recur is functional, and its use in the tail position is verified by the compiler.

Answer 2

According to clojure.org

There is no tail optimization optimization, use recur.

Therefore, for this you need to use a special form "recur".