Recursively reverse a sequence in Clojure

Question

I want to reverse a sequence in Clojure without using the reverse function, and do so recursively.

Here is what I came up with:

(defn reverse-recursively [coll]
  (loop [r (rest coll)
         acc (conj () (first coll))]
    (if (= (count r) 0)
      acc
      (recur (rest r) (conj acc (first r))))))

Sample output:

user> (reverse-recursively '(1 2 3 4 5 6))
(6 5 4 3 2 1)
user> (reverse-recursively [1 2 3 4 5 6])
(6 5 4 3 2 1)
user> (reverse-recursively {:a 1 :b 2 :c 3})
([:c 3] [:b 2] [:a 1])

Questions:

1. Is there a more concise way of doing this, i.e. without loop/recur?
2. Is there a way to do this without using an "accumulator" parameter in the loop?

---

References:

Whats the best way to recursively reverse a string in Java?

http://groups.google.com/group/clojure/browse_thread/thread/4e7a4bfb0d71a508?pli=1

Answer 1

• You don't need to count. Just stop when the remaining sequence is empty.
• You shouldn't pre-populate the acc, since the original input may be empty (and it's more code).
• Destructuring is cool.

(defn reverse-recursively [coll]
  (loop [[r & more :as all] (seq coll)
         acc '()]
    (if all
      (recur more (cons r acc))
      acc)))

As for loop/recur and the acc, you need some way of passing around the working reversed list. It's either loop, or add another param to the function (which is really what loop is doing anyway).

Or use a higher-order function:

user=> (reduce conj '() [1 2 3 4])
(4 3 2 1)

Answer 2

For the sake of exhaustivenes, there is one more method using into. Since into internally uses conj it can be used as follows :

(defn reverse-list 
  "Reverse the element of alist."
  [lst]
  (into '() lst))