Clojure 中的基本树递归

Question

我想知道是否有人可以帮助我，因为我遇到了这段代码的障碍。我的代码如下所示。

当我运行跟踪时，它会在命中 nil 值时停止，有人知道哪里出了问题吗？

这是我的数据：

'(1 ( -2 17 (4)) -8 (6 13)))

代码：

(defn tree? [t]
  (and (seq t) (not (empty? t))))

(defn bounds2
  ([tree] (bounds2 tree 99 -99))
  ([tree minVal maxVal]
   (cond
     (number? tree) tree
     (tree? tree)
     (cond

       (nil? (bounds2 (first tree) minVal maxVal))
       (bounds2 (rest tree) minVal maxVal)

       ((complement nil?) (bounds2 (first tree) minVal maxVal))
       (cond
         (< (bounds2 (first tree) minVal maxVal) minVal)
         (recur (rest tree) (first tree) maxVal)

         (> (bounds2 (first tree) minVal maxVal) maxVal)
         (recur (rest tree) minVal (first tree)))

       (empty? tree) nil))))

Answer 1

你这里有几个问题。最直接的一个是你实际上从未 return 任何界限。 cond 语句的每个可能的退出点要么是某种未修改的递归调用、一个数字，要么是 nil。从逻辑上讲，您在某些时候需要 return 类似 [minVal maxVal] 的东西，并且您应该期望所有对 return 某种格式的递归调用。当然，这会使您的比较逻辑变得相当复杂。

其他要点包括 tree? 在逻辑上等同于 seq（正如评论中指出的那样），并且您的 (empty? tree) 子句是死代码，因为 tree 永远不能同时满足 tree? = seq 和 empty?。（事实证明，(bounds2 '())仍然是returns nil，但这是因为cond returns nil如果你没有匹配就失败了任何子句。)

如果您能原谅全部重写，我认为这可以满足您的需求，与您的原始代码几乎相同。（你在评论中提到你不想使用 flatten，所以我避免了那个和中间 reduce 解决方案）。

(defn bounds2 [tree]
  (loop [[x & more :as tree] tree, minVal 99, maxVal -99]
    (cond
      (empty? tree)  [minVal maxVal]
      (number? x)    (recur more (min x minVal) (max x maxVal))
      (seq x)        (recur (concat x more) minVal maxVal))))

我的大部分更改都是风格上的（使用 loop 而不是多个参数；解构；取消嵌套 cond 语句）；这里逻辑上的一个主要变化是我们使用 concat 到“flatten as we go”。同样重要的是要注意，对我们所有的递归调用使用 recur 将有助于防止我们炸毁堆栈。

Clojure 中的基本树递归

Basic tree recursion in Clojure

tree

clojure