如何在Clojure中递归计算树结构的深度？

Question

所以我对 Clojure 有一个非常基本的了解，并想计算使用包含向量本身的向量定义的树的深度。例如，[1 [2] [3 [4] ]] 表示一棵树，其中 1 是根，而 [2] 是 1 的子树，而 [3 [4]] 是子树。

(defn height[tree]
(if(empty? tree)
    (1); Base case
    (inc (apply max (map  height (next tree))))); Calculate the height for every subtree and return maximum
)

我认为这种方法会起作用，因为它应该递归计算每个子树的深度以返回最大值。但是，当我尝试运行此方法时，出现非法参数异常。

Answer 1

带拉链的尾递归变体：

(require '[clojure.zip :as z])

(defn height-2 [tree]
  (loop [curr (z/zipper coll? seq nil tree) h 0]
    (if (z/end? curr) h
        (recur (z/next curr)
               (if (z/branch? curr) h
                   (-> curr z/path count (max h)))))))

在回复：

user> (height-2 [1 [2] [3 [4] ]])
3
user> (height-2 (nth (iterate (partial vector 1) []) 1000))
1000
user> (height-2 (nth (iterate (partial vector 1) []) 100000))
100000