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=> 

スタックの深さが小さいため、ここでは明らかにこれで問題ありません。しかし、私が返したいリストを作成しているこの一般的なタイプの問題では、再帰呼び出しは常にコンス呼び出し内で終了します。これを末尾再帰に変換して、再帰を使用し、スタック スペースを使用しないようにするにはどうすればよいでしょうか。

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))

2位

(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))))))