When to use pure recursion and when to use loop/recur?

Question

"pure recursion" is a made-up term here, please forgive.

Here are two examples using two different recursion approaches. What are the guidelines of usage of one over another?

(defn take-while
  "Returns a lazy sequence of successive items from coll while
  (pred item) returns true. pred must be free of side-effects."
  {:added "1.0"
   :static true}
  [pred coll]
  (lazy-seq
   (when-let [s (seq coll)]
       (when (pred (first s))
         (cons (first s) (take-while pred (rest s)))))))

(defn take-last
  "Returns a seq of the last n items in coll.  Depending on the type
  of coll may be no better than linear time.  For vectors, see also subvec."
  {:added "1.1"
   :static true}
  [n coll]
  (loop [s (seq coll), lead (seq (drop n coll))]
    (if lead
      (recur (next s) (next lead))
      s)))

Answer 1

A few factors to consider:

• loop/recur doesn't consume stack space - so it's the right choice if you are going to do deeply nested recursion that might otherwise cause a StackOverflowError
• loop/recur is faster - it's one of the most efficient constructs in Clojure, done correctly it should match the speed of an equivalent for loop in Java code
• normal recursion is more idiomatic - on average it tends to give you clearer, more functional code whereas loop/recur tends to push you more towards an imperative, iterative style
• loop/recur has more restrictions - you can only recur in tail position, you can't do mutual recursion between two different functions, etc. Sometimes it simply isn't possible to make loop/recur work, at other times you may need to contort your code to do so.

Answer 2

The only one reason to use lazy-seq/lazy-cons mechanism is generating lazy sequences. If you don't need them then loop/recur should undoubtedly be used.

Answer 3

Use plain recursion when you are writing your function in the first place. Then change this to recur once you have it all working, if you can.

One problem with TCO is that if you balk your recursion up, you get an infinite look. Without, your code crashes nicely with a stack overflow, which is what you want. I didn't like the idea of recur when I first heard about it --most optimisations should just happen -- but being able to switch it off is nice.