Clojure: Can only recur from tail position

23
votes

I'm trying to recursively reverse a list, but am getting Can only recur from tail position upon run. What does this mean precisely and how can my code be improved so it works?

(defn recursive-reverse [coll]
  (loop [coll coll]
    (if (< (count coll) 2) '(coll)
      (conj (first coll) (recur (rest coll)))
      )))

EDIT

Output for Oscar's solution. It works for lists but not vectors?

user=> (= (recursive-reverse [1 2 3 4 5]) (recursive-reverse '(1 2 3 4 5)))
false
user=> (= '(1 2 3 4 5) [1 2 3 4 5])
true
user=> (recursive-reverse [1 2 3 4 5])
[1 2 3 4 5]
user=> (recursive-reverse '(1 2 3 4 5))
(5 4 3 2 1)
3
recursionclojure
it works differently for lists and vectors because conj works differently for both. It's cheapest to "add" item to the front of a list, and to the end of a vector. conj looks at the type of collection and adds it in the cheapest way. To be honest this never felt quite right to me, but I'm sure Rich Hickey and the other Clojure devs have thought very thoroughly about it and decided the pros outweigh any cons. - Gert
Fascinating. I guess performance was their number one propriety for the basic operations, but yes that seems strange. - Chris
Spot on, @Gert. I updated my answer, I'd rather return the correct answer of a different type than an incorrect answer if the input is a vector - Óscar López

3 Answers

23
votes

The error Can only recur from tail position means that you're not calling recur as the last expression in the recursive part of the function - in fact, in your code conj is the last expression.

Some improvements to make your code work:

  • Ask if the collection is empty as the base case, instead of comparing if its length is less than two
  • conj receives a collection for its first parameter, not an element
  • It's a better idea to use cons instead of conj (which adds new elements at different places depending on the concrete type of the collection, according to the documentation). In this way the returned collection will be reversed if the input collection is either a list or a vector (although the type of the returned collection will always be clojure.lang.Cons, no matter the type of the input collection)
  • Be aware that '(coll) is a list with a single element (the symbol coll) and not the actual collection
  • For correctly reversing a list you need iterate over the input list and append each element to the beginning of an output list; use an accumulator parameter for this
  • For taking advantage of tail-recursion call recur at the tail position of the function; in this way each recursive invocation takes a constant amount of space and the stack won't grow unbounded

I believe this is what you were aiming for:

(defn recursive-reverse [coll]
  (loop [coll coll
         acc  (empty coll)]
        (if (empty? coll)
            acc
            (recur (rest coll) (cons (first coll) acc)))))
7
votes

You can only call recur from tail position in Clojure. It's part of the design of the language, and is a restriction related to the JVM.

You can call your function name (using recursion) without using recur, and depending on how you structure your program, like whether you use lazy sequences or not, you might not have the stack blow up. But you are better off using recur, and using loop with recur allows you some local bindings.

Here's an example from 4Clojure.com where recursion is used without recur.

(fn flt [coll]
  (let [l (first coll) r (next coll)]
    (concat 
      (if (sequential? l)
        (flt l)
        [l])
      (when (sequential? r)
        (flt r)))))
2
votes

The easiest way to make your code work is to use the function name instead of recur:

(defn recursive-reverse [coll]
  (loop [coll coll]
    (if (< (count coll) 2) '(coll)
      (conj (first coll) (recursive-reverse (rest coll)))
      )))

It will make the call stack huge and error out for large enough inputs, of course.

Here's another way to write a tail-call-friendly version of recursive-reverse:

(defn recursive-reverse [s]
  (letfn [
    (my-reverse [s c]
      (if (empty? s)
        c
        (recur (rest s) (conj c (first s)))))]
    (my-reverse s '())))

It pulls items off the head of the input list and adds them to the head of the accumulator list.

'Tail position' just means that the recur is the last thing done by the function before it returns. This differs from your 'natural recursion' solution in which there's still work being done by the function in between calling itself and returning.