Would loop and recur exist if Clojure was build on top language with no StackOverflows?

Here’s a silly example to illustrate the difference between a tail recursive function and one that’s not. TCO won’t be performed on either, since Clojure quite reasonably doesn’t perform TCO. I want to illustrate the concept, though, and Clojure is familiar here. If we translated the code into another language TCO might be performed.

(defn oh-no-1 [] (println "Oh, no!  We found a zero!!") nil)

;; not tail-recursive
(defn classify-until-zero-1
  [xs]
  (let [x (first xs)]
    (cond (empty? xs) nil
          (pos? x)  (cons :p (classify-until-zero-1 (rest xs)))
          (neg? x)  (cons :n (classify-until-zero-1 (rest xs)))
          (zero? x) (oh-no-1))))

(defn oh-no-2 [results] (println "Oh, no!  We found a zero!!") results)

;; tail-recursive
(defn classify-until-zero-2
  [acc xs]
  (let [x (first xs)]
    (cond (empty? xs) nil
          (pos? x)  (classify-until-zero-2 (conj acc :p) (rest xs))
          (neg? x)  (classify-until-zero-2 (conj acc :n) (rest xs))
          (zero? x) (oh-no-2 acc))))

Here they are in action:

user=> (classify-until-zero-1 [1 -1 2 -2 0 3 -3])
Oh, no!  We found a zero!!
(:p :n :p :n)
user=> (classify-until-zero-2 [] [1 -1 2 -2 0 3 -3])
Oh, no!  We found a zero!!
[:p :n :p :n]

The tail recursive calls are in classify-until-zero-2, in the lines beginning with (pos? and (neg?. Notice that nothing has to happen after the recursive calls return, even though they are not at the end of the function definition. (classify-until-zero-2 has an extra argument, acc, for accumulator. You can avoid this by wrapping the function in another function, for example.)

By contrast, in classify-until-zero-1, a cons has to be performed after the recursive call returns. That’s why it’s not tail recursive: there is a function waiting to act. Those waiting function calls will build up on the stack. When TCO is possible, as in classify-until-zero-2, the stack can be manipulated by the compiler so that that doesn’t happen.

I included two recursive calls in each function to show that tail recursion doesn’t necessarily have to do with a single recursive call. I included the oh-no functions to show that there can be other branches that call other functions, without necessarily breaking tail recursion. (I didn’t illustrate mutual tail-recursion.)