clojure - 将递归函数转换为使用尾递归

Question

假设我有这样的功能：

user=> (def m {10 5, 5 2, 2 1})
#'user/m
user=> (defn hierarchy [x] (when x (cons x (hierarchy (get m x)))))
#'user/hierarchy
user=> (hierarchy 10)
(10 5 2 1)
user=> 

显然这在这里很好，因为堆栈深度会很小。但是对于这种一般类型的问题，我正在构建一个我想要返回的列表，递归调用总是在 cons 调用中结束。我如何将其转换为尾递归，以便我可以使用递归而不占用堆栈空间？

Answer 1

阅读蓄电池。

在 Clojure 中，这个特定问题可以通过使用lazy-seq. lazy-seq推迟计算，因此堆栈溢出（通常）不是问题。

(defn hierarchy
  [x]
  (when x
    (lazy-seq
      (cons x (hierarchy (get m x))))))

Answer 2

您可以在不使用递归的情况下优雅地解决这个问题：

(defn hierarchy [x]
  (take-while identity (iterate m x)))

Answer 3

第一种变体

(defn hierarchy* [res x]
  (if-not x
    res
    (recur (conj res x) (get m x))))

(defn hierarchy [x]
  (hierarchy* [] x))

第二

(defn hierarchy [x]
  (loop [res []
         next-x x]
    (if-not next-x
      res
      (recur (conj res next-x) (get m next-x)))))

Answer 4

添加lazy-seq：

(defn hierarchy [x] (when x (cons x (lazy-seq (hierarchy (get m x))))))