How can I call recur in an if conditional in Clojure?

Question

I'm trying to solve the count a sequence excercise at 4clojure.com. The excercise is to count the number of elements in a collection without using the count function.

I thought I can do this via recursion, by the usage of rest. If what I get isn't empty, I return 1 + recur on the sequence rest returned. The problem is, that I end up getting

java.security.PrivilegedActionException: java.lang.UnsupportedOperationException:
Can only recur from tail position

even though I'm calling recur as the very last statement.

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

Am I missing something?

Answer 1

The last statement is the addition, not the call to recur, which is why it doesn't work. The fact that it's inside an if has nothing to do with it. (fn [coll] (let [tail (rest coll)] (+ 1 (recur tail)))) wouldn't work either.

The usual way to turn a function like this into a tail-recursive one is to make the function take a second argument, which holds the accumulator for the value you're adding up and then recurse like this: (recur tail (+ acc 1)) instead of trying to add 1 to the result of recur.

As a general rule: If you're doing anything to the result of recur (like for example adding 1 to it), it can't be in a tail position, so it won't work.