Clojure: What exactly is tail position for recur?
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.
Just to supplement the excellent answer from Paul above, The Joy of Clojure (ed1) provides a table (Table 7.1) that shows exactly where tail position is in various forms/expressions, which I've reproduced below. Look for where the word "tail" occurs in each form/expression:
|---------------------+-------------------------------------------+---------------| | Form | Tail Position | recur target? | |---------------------+-------------------------------------------+---------------| | fn, defn | (fn [args] expressions tail) | Yes | | loop | (loop [bindings] expressions tail) | Yes | | let, letfn, binding | (let [bindings] expressions tail) | No | | do | (do expressions tail) | No | | if, if-not | (if test then tail else tail) | No | | when, when-not | (when test expressions tail) | No | | cond | (cond test test tail ... :else else tail) | No | | or, and | (or test test ... tail) | No | | case | (case const const tail ... default tail) | No | |---------------------+-------------------------------------------+---------------|