在Clojure中递归地反转一个序列

Question

我想在Clojure中递归地反转一个序列，但不使用reverse函数。

这是我想到的代码：

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

示例输出：

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

问题：

1. 有没有更简洁的方法来做这件事，比如不使用循环/递归？
2. 有没有一种方法在循环中不使用“累加器”参数来完成这个任务？

---

参考：

在Java中递归地反转字符串的最佳方法是什么？

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

- noahlz

---

你可能在尝试解决这个4clojure问题吗？ :) - Drew Noakes

不，我不是。"递归地反转一个字符串" 是一个非常常见的面试问题。 - noahlz

Answer 1

• 不需要计数，当剩余序列为空时停止。
• 不应该预先设定acc, 因为原始输入可能为空（而且代码更多）。
• Destructuring 很酷。

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

关于 loop/recur 和 acc，你需要一些方法来传递工作中的反转列表。这要么是使用 loop，要么是将另一个参数添加到函数中（这实际上就是 loop 在做的事情）。

或者使用高阶函数：

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

- Alex Taggart

---

关于“使用高阶函数”，请查看（源反转）(source reverse)。 - noahlz

当应用map({:a 1 :b 2 :c 3})时，REPL会中止该函数。 - BLUEPIXY

技术上说，我的问题是“反转一个序列”，而不是“反转任何东西，包括地图”，所以我认为这个问题并没有排除它。顺便说一下，这是错误信息：Clojure> (reverse-recursively {:a 1 :b 2}) java.lang.UnsupportedOperationException: nth not supported on this type: PersistentArrayMap - noahlz

此外，在Clojure中，循环/递归当然需要尾递归，但它被认为是“代码异味”：http://twoguysarguing.wordpress.com/2010/07/26/7-rules-for-writing-clojure-programs/ - noahlz

@noahz实际上这篇文章说“循环/递归不是代码异味，但要对它保持怀疑态度”。我猜他们的意思是一般情况下优先选择map、reduce等方式，但并不总是提供解决方案。 - Adrian Mouat

Answer 2

为了全面，这里还有一种使用 into 的方法。由于 into 内部使用 conj，因此可以按以下方式使用：

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

- pankajdoharey

Answer 3

是的，针对第一个问题，以下是我对递归谜题的回答（我无法确定这是否是良好的Clojure实践）：

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

- Fredrick Pennachi

---

尝试一下这个：(recursive-reverse (apply str (seq (take 100000 (repeat "foo"))))) - noahlz

好的，我刚刚做到公案的最后一部分，那里阶乘函数会溢出，如果你不使用循环/递归结构。所以我想现在可以说这不是一个好的实践 :) - 干杯！ - Fredrick Pennachi

这真的很优雅！ - daGrevis

Answer 4

在当前版本的Clojure中，有一个名为rseq的内置函数。对于任何经过的人来说。

- user1648311

---

rseq 要求输入序列必须是 Reversible，这使得它通常不适用于 cons 列表、PersistentList、LazySeq 和字符串。它旨在优化可以在常数时间内反转的序列。 - omiel

Answer 5

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

- zongwu233

Answer 6

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

问题1。

JVM 无法优化递归，递归函数会直接并导致堆栈溢出。因此，在Clojure中，使用loop/recur。因此，必须使用不使用递归的函数来定义深度递归（也用作函数trampoline的内部使用）。

问题2。

通过recur实现递归函数时，必须是尾递归的。如果将普通递归函数改变为尾递归函数，则需要传递一个变量值作为累加器。

- BLUEPIXY

---

映射序列的顺序不会改变执行顺序，但是顺序需要被实现。 - BLUEPIXY

我不明白你的评论。“订单将被实施？” - noahlz

@noahz，(rev {:a 1 :b 2 :c 3}) ->（[:c 3] [:b 2] [:a 1]）并不一定正确。我在Clojure1.3.0中的结果是（[:b 2] [:c 3] [:a 1]）。 - BLUEPIXY

е•ҠпјҢеӣ дёәClojureдёӯзҡ„PersistentArrayMapеғҸjava.util.HashMapдёҖж ·жҳҜж— еәҸзҡ„пјҹиҝҷеҫҲдёҚзӣҙи§ӮгҖӮ - noahlz

我知道。通常情况下，映射不确定顺序。为了使它们按照示例中所示插入，必须这样做。 - BLUEPIXY

Answer 7

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

- Jiacai Liu