说我有一个这样的功能:
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调用结束。我如何将其转换为尾递归,以便可以使用递归而不占用堆栈空间?
最佳答案
第一变种
(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)))))