我试图递归地反转一个列表,但在运行时得到了Can only recur from tail position
。这到底是什么意思,我的代码如何改进才能正常工作?
(defn recursive-reverse [coll]
(loop [coll coll]
(if (< (count coll) 2) '(coll)
(conj (first coll) (recur (rest coll)))
)))
编辑
Oscar解决方案的输出。它适用于列表,但不适用于向量?
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)
发布于 2012-06-03 01:18:10
在Clojure中,您只能从尾部位置调用recur。这是语言设计的一部分,也是与JVM相关的限制。
您可以在不使用recur的情况下调用您的函数名(使用递归),并且根据您的程序结构,例如您是否使用惰性序列,您可能不会使堆栈崩溃。但是您最好使用recur,并且使用loop with 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)))))
发布于 2012-06-03 03:40:08
使代码正常工作的最简单方法是使用函数名而不是recur
(defn recursive-reverse [coll]
(loop [coll coll]
(if (< (count coll) 2) '(coll)
(conj (first coll) (recursive-reverse (rest coll)))
)))
当然,这会使调用堆栈变得庞大,并且对于足够大的输入会产生错误。
下面是编写对尾部调用友好的递归-反向版本的另一种方法:
(defn recursive-reverse [s]
(letfn [
(my-reverse [s c]
(if (empty? s)
c
(recur (rest s) (conj c (first s)))))]
(my-reverse s '())))
它从输入列表的头部拉出项目,并将它们添加到累加器列表的头部。
“尾部位置”仅仅意味着recur
是函数在返回之前所做的最后一件事。这与你的“自然递归”解决方案不同,在“自然递归”解决方案中,函数在调用自身和返回之间仍有工作要做。
https://stackoverflow.com/questions/10864172
复制相似问题