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))

Answer 3

Yes to question 1, this is what I came up with for my answer to the recursion koan (I couldn't tell you whether it was good clojure practice or not).

(defn recursive-reverse [coll]
    (if (empty? coll)
        []
        (conj (recursive-reverse (rest coll)) (first coll) )))

Answer 4

In current version of Clojure there's a built-in function called rseq. For anyone who passes by.

Answer 5

(defn my-rev [col]
  (loop [ col col
          result []]
        (if (empty? col)
            result
            (recur (rest col) (cons (first col) result)))))

Q1.

The JVM can not optimize the recursion, a recursive function that would directly and stack overflow. Therefore, in Clojure, which uses the loop/recur. So, without using a function that recur deep recursion can not be defined. (which is also used internally to recur as a function trampoline.)

Q2.

a recursive function by recur, must be tail-recursive. If the normal recursive function change to tail-recursive function, so there is a need to carry about the value of a variable is required as the accumulator.

Answer 6

(defn reverse-seq [sss]
  (if (not (empty? sss))
    (conj (reverse-seq (rest sss)) (first sss))
  )
)

Answer 7

(defn recursive-reverse [coll]
  (if (empty? coll)
    ()
    (concat (vector (peek coll)) (recursive-reverse (pop coll )))
  )
)
and test:
user=> (recursive-reverse [1])       
(1)
user=> (recursive-reverse [1 2 3 4 5])
(5 4 3 2 1)