23

我正在尝试递归地反转列表，但正在 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)
4

3 回答 3

23

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

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

  • 询问集合是否为空作为基本情况，而不是比较其长度是否小于两个
  • 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)))))
于 2012-06-02T18:22:21.113 回答
7

您只能从 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)))))
于 2012-06-02T17:18:09.867 回答
2

使您的代码工作的最简单方法是使用函数名称而不是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函数在返回之前所做的最后一件事。这与您的“自然递归”解决方案不同，在该解决方案中，函数在调用自身和返回之间仍有工作要做。

于 2012-06-02T19:40:08.440 回答