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

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
   开发者_JAVA百科            (+ 1 (recur tail)))))

Am I missing something?

---

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.

---

The error that you are getting is pointing out that your final expression of (+ 1 (recur tail)) is not tail-call-optimization optimizable (is that a word?). The problem is that it needs to keep a bunch of (+ 1 ...) expressions on the stack in order to evaluate result of the function. Tail call optimization can only occur if the value of the called function is the only thing needed to know the return of the function making the call.

What you are trying to write is pretty much a fold. In this case the function should pass along the rest of the collection as well as the count so far.

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