Clojure:只能从尾部位置重复出现

Question

我试图以递归方式反转列表,但我正在 Can only recur from tail position运行.这是什么意思,我的代码如何改进,以便它的工作？

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

编辑

奥斯卡解决方案的输出.它适用于列表但不适用于矢量？

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)

Answer 1

该错误Can only recur from tail position意味着您不是recur在函数的递归部分中调用最后一个表达式 - 实际上,在您的代码中conj是最后一个表达式.

一些改进使您的代码工作:

• 询问集合是否为空基础情况,而不是比较其长度是否小于2
• conj接收第一个参数的集合,而不是元素
• 根据文档,使用cons而不是conj(根据集合的具体类型在不同的地方添加新元素)是一个更好的主意.这样,如果输入集合是列表或向量,则返回的集合将被反转(尽管返回集合的类型将始终为,无论输入集合的类型如何)clojure.lang.Cons
• 请注意,这'(coll)是一个包含单个元素(符号coll)的列表,而不是实际的集合
• 要正确反转列表,您需要遍历输入列表并将每个元素附加到输出列表的开头; 为此使用累加器参数
• 为了利用recur函数尾部位置的尾递归调用; 通过这种方式,每次递归调用都会占用一定量的空间,并且堆栈不会无限增长

我相信这是你的目标:

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

Answer 2

你只能在Clojure中从尾部位置调用recur.它是语言设计的一部分,是与JVM相关的限制.

您可以在不使用recur的情况下调用函数名称(使用递归),并且根据您的程序结构,例如是否使用惰性序列,您可能没有堆栈爆炸.但是你最好使用recur,并且使用带有recur的循环允许你进行一些本地绑定.

这是4Clojure.com的一个例子,其中使用递归而不重复.

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