Я хочу напечатать двоичное дерево вНьюик формат, показывая расстояние каждого узла до его родителя. На данный момент у меня не было проблем со следующим кодом, который использует обычную рекурсию, но слишком глубокое дерево может привести к переполнению стека.

(defn tree->newick
  [tree]
  (let [{:keys [id children to-parent]} tree
        dist (double to-parent)] ; to-parent may be a rational
    (if children
      (str "(" (tree->newick (first children)) 
           "," (tree->newick (second children)) 
           "):" dist)
      (str (name id) ":" dist))))

(def example {:id nil :to-parent 0.0 
              :children [{:id nil :to-parent 0.5 
                          :children [{:id "A" :to-parent 0.3 :children nil}
                                     {:id "B" :to-parent 0.2 :children nil}]}
                         {:id "C" :to-parent 0.8 :children nil}]})

(tree->newick example)
;=> "((A:0.3,B:0.2):0.5,C:0.8):0.0"

(def linear-tree (->> {:id "bottom" :to-parent 0.1 :children nil}
                   (iterate #(hash-map :id nil :to-parent 0.1 
                                       :children [% {:id "side" :to-parent 0.1 :children nil}]))
                   (take 10000)
                   last))

(tree->newick linear-tree)
;=> StackOverflowError

Проблема, которую я нашел с текущими утилитами, такими какtree-seq а такжеclojure.walkявляется то, что я должен посетить внутренний узел более одного раза, чтобы вставить запятую и закрыть скобку. Я использовалclojure.zip, но мне не удалось написать ленивую / хвостовую рекурсивную реализацию, так как мне нужно было бы хранить для каждого внутреннего узла, сколько раз они уже были посещены.