Clojure: What exactly is tail position for recur?

Question

What's the precise definition of "tail position" for recur in Clojure? I would think that it would be the last item in a loop S-expression, but in the example below it seems to me that the S-Expression which starts with (if ...) is in tail position i.e. (loop [binding statements] [if statement]).

(= __   (loop [x 5          result []]     (if (> x 0)       (recur (dec x) (conj result (+ 2 x)))       result))) 

(Code taken from http://www.4clojure.com/problem/68)

Closely related question: How can I call recur in an if conditional in Clojure?

Answer 1

The tail position is a position which an expression would return a value from. There are no more forms evaluated after the form in the tail position is evaluated.

Consider this example from The Joy of Clojure

(defn absolute-value [x]   (if (pos? x)       x        ; "then" clause        (- x)))  ; "else" clause 

It takes a single parameter and names it x. If x is already a positive number, then x is returned; otherwise the opposite of x is returned. The if form is in the function’s tail position because whatever it returns, the whole function will return. The x in the “then” clause is also in a tail position of the function. But the x in the “else” clause is not in the function’s tail position because the value of x is passed to the - function, not returned directly. The else clause as a whole (- x) is in a tail position.

Similarly in the expression

(if a     b     c) 

both b and c are in tail positions, because either of them could be returned from the if statement.

Now in your example

(loop [x 5        result []]   (if (> x 0)     (recur (dec x) (conj result (+ 2 x)))     result))) 

the (if ...) form is in the tail position of the (loop ...) form and both the (recur ...) form and the result form are in the tail position of the (if ...) form.

On the other hand in the question that you linked

(fn [coll] (let [tail (rest coll)]              (if (empty tail)                  1                  (+ 1 (recur tail))))) 

the recur is not in tail position because the (+ 1 ...) will be evaluated after the (recur tail). Therefore the Clojure compiler gives an error.

Tail position is important because you can use the recur form from tail position. Functional programming languages usually use recursion for what procedural programming languages accomplish by loops. But recursion is problematic, because it consumes stack space and deep recursion can lead to stackoverflow problems (in addition to being slow). This problem is usually solved by tail call optimization (TCO), which does away with the caller when the recursive call happens in the tail position of a function / form.

Because Clojure is hosted on the JVM and the JVM does not support tail call optimization, it needs a trick to do recursion. The recur form is that trick, it allows the Clojure compiler to do something similar to tail call optimization. In addition, it verifies that recur is indeed in a tail position. The benefit is that you can make sure that the optimization actually does happen.