Why does this overflow the stack instead of using tail recursion?

Question

I've 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 outputs from my recursion 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 don't understand why I get a StackOverflowError. The last thing that recurse-n-times does is call itself, so I expect it to use tail recursion and not grow the stack at all.

I would expect this alternate 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 does recurse-n-times not use tail recursion?

Answer 1

This is a limitation of the JVM, not of Clojure. JVM doesn't 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

recur form should appear at the tail position otherwise the Clojure compiler will complain about it.

Note that recur is the only non-stack-consuming looping construct in Clojure. There is no tail-call optimization and the use of self-calls for looping of unknown bounds is discouraged. recur is functional and its use in tail-position is verified by the compiler.

Answer 2

According to clojure.org

There is no tail-call optimization, use recur.

So you must use "recur" special form to do that.