CODEWITHSUNDEEP
recursionclojure
noahlz
noahlz

Reputation: 10311

Recursively reverse a sequence in Clojure

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

Upvotes: 11

Views: 11707

Answers (7)

pankajdoharey
pankajdoharey

Reputation: 1572

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

Upvotes: 6

zongwu233
zongwu233

Reputation: 13

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

Upvotes: 0

Jiacai Liu
Jiacai Liu

Reputation: 2743

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

Upvotes: 0

user1648311
user1648311

Reputation:

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

Upvotes: 2

Fredrick Pennachi
Fredrick Pennachi

Reputation: 842

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

Upvotes: 4

Alex Taggart
Alex Taggart

Reputation: 7825

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

Upvotes: 27

BLUEPIXY
BLUEPIXY

Reputation: 40145

(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.

Upvotes: 0

Related Questions