recur in the rightful tail poistion

Question

recur should be called in the tail position and I assume that it effectively acts as non-recursive quasi-loop.

Is expr-1 or 2 regarded in the rightful tail position but none of expr-3 till 8 in the following mimic block structures? Otherwise, how to reason and identify it before resort to trail and error?

(defn foo [x]
 (if cond-expr-1
  (recur expr-1)
  (recur expr-2)))

(defn bar [x]
 (if cond-expr-2
  (fn-1 (recur expr-3))
  (fn-2 (recur expr-4))))

(defn baz [x]
 (if cond-expr-3
  (if cond-expr-4  
    (recur expr-5)
    (recur expr-6))
  (if cond-expr-5  
    (recur expr-7)
    (recur expr-8))))

Answer 1

In the case of expr-3 and expr-4, it is the argument of a function, and that is why it is not in tail position.

Calling recur is basically like a goto or return statement, both of which cannot be used inside a function argument list.

Since the if expression is not a function (it is a "special form"), there is no problem as with a function arg list.

---

Here is a comparison between loop/recur and a more imperative approach using while:

(ns tst.demo.core
  (:use tupelo.core tupelo.test))

(defn fib-recur
  [arg]
  (assert (and (int? arg) (pos? arg)))
  ; initialize state vars
  (loop [N      arg
         result 1]
    (if (zero? N)
      result
      ; compute next state vars
      (let [N-next      (dec N)
            result-next (* result N)]
        (recur N-next result-next))))) ; jump to top of loop with next state vars

(defn fib-while
  [arg]
  (assert (and (int? arg) (pos? arg)))
  ; initialize state vars
  (let [state (atom {:N      arg
                     :result 1})]
    (while (pos? (:N @state)) ; must use newest state value for N in test
      ; compute next state vars
      (let [N          (:N @state)
            result     (:result @state)
            state-next {:N      (dec N)
                        :result (* result N)}]
        (reset! state state-next))) ; save new state & jump to top of loop
    (:result @state)))

(dotest
  (is= 120 (fib-recur 5))
  (is= 120 (fib-while 5)))

Answer 2

An expression is in tail position if there is nothing else to be evaluated in the current function following that expression. In your case, all the recur invocations in foo and baz are in tail position and thus both functions will compile fine.

In bar, however, neither of the recur invocations will be allowed because neither of expr-3 or expr-4 are in tail position. There are function calls which uses the result of each recur invocation as an argument - that is, the function call logically follows the recur invocation, and thus recur is not in tail position.

This is not to say that you can't write bar to make a recursive invocation of itself, but you have to code it explicitly, as in:

(defn bar [x]
 (if cond-expr-2
  (fn-1 (bar expr-3))
  (fn-2 (bar expr-4))))

This is absolutely allowed, BUT these recursive invocations of bar will consume stack space which means that if the function calls itself recursively enough times you'll run out of stack space. recur (and tail recursion in general) is valuable because it doesn't involve making a function call in the traditional sense - instead, (speaking logically here) the function argument on the stack is replaced with the new argument and the code jumps back to the beginning of the function, so no stack space is used. Of course, this means that the original argument in the first call to the function is lost.

Other versions of Lisp do not use the recur keyword. When these versions of Lisp find that a function is calling itself recursively they make the same "tail position" determination which Clojure makes and if they find that the call is in tail position they perform the same "replace-the-argument-and-jump" logic Clojure does, while if they find that the call is not in tail position they emit code to perform a "real" recursive call, rather than failing the compilation. Clojure's advantage is that it makes it very obvious to the developer if a call will be compiled as a tail-recursive call (branch) or not.