TL;DR
- 相互再帰は引数の大きさに比例したスタックを消費し、自己再帰ではないので
recurも使えない。 - 非再帰的に解くアプローチは 4 つある。複数の概念をまとめる抽象化で自己再帰に書き換える、
trampolineを使う、再帰呼び出しをlazy-seqで包む、メモ化して値をシーケンスとして定義する。
内容
相互再帰
相互再帰とは、2 つ以上の関数が互いを呼び合う再帰である。簡単な例として、相互再帰を使って my-odd? と my-even? を定義してみる。
(declare my-odd? my-even?)
(defn my-odd? [n]
(if (zero? n)
false
(my-even? (dec n))))
(defn my-even? [n]
(if (zero? n)
true
(my-odd? (dec n))))my-odd? と my-even? はそれぞれ互いを呼び出しているので、2 つの var を定義前に作る必要がある。def でもよいが、declare マクロを使うと、1 行で 2 つの var を初期値なしで作れる。
これらの関数は小さな値に対しては動作する。
(map my-even? (range 10))
; (true false true false true false true false true false)
(map my-odd? (range 10))
; (false true false true false true false true false true)しかし、これらは引数の大きさに比例したスタックを消費するので、大きな値を与えると動作しない。
(my-even? (* 1000 1000 1000))
; java.lang.StackOverflowErrorこの問題は末尾再帰での問題と同じである。しかし、今回は自己再帰ではないので、recur を使えない。
再帰的な問題を非再帰解法で解くための 4 つのアプローチ
一般的に、再帰的な問題に対して、非再帰的な解法は簡単には見つからない。ここでは、次の 4 つのアプローチを考える。
- 自己再帰への書き換え
- トランポリンによる相互再帰
- 再帰を遅延評価で置き換える
- メモ化で再帰を止める
1. 自己再帰への書き換え
相互再帰は互いに関係している複数の概念をモデル化するのに役立つ。ここで、複数の概念を一度に扱える抽象化が見つけられれば、相互再帰を自己再帰に変換できる。
たとえば奇数と偶数は、パリティの概念を導入すれば 1 つにまとめられる。recur を使って、偶数に対しては 0、奇数に対しては 1 を返す関数 parity を定義する。
(defn parity [n]
(loop [n n par 0]
(if (= n 0)
par
(recur (dec n) (- 1 par)))))これを使えば、my-odd? と my-even? を定義するのは簡単である。
(defn my-even? [n] (= 0 (parity n)))
(defn my-odd? [n] (= 1 (parity n)))今回は単純だったが、多くの相互再帰では、自己再帰への変換を見つけるのは容易ではない。相互再帰を自己再帰に変換しようとして、たくさんの条件判断が入ってきて定義が複雑になったら、このアプローチは避けたほうがよい。
2. トランポリンによる相互再帰（trampoline）
トランポリンは相互再帰を最適化するテクニックで、事後的な recur のようなものである。つまり、関数の実装者ではなく、関数を呼び出す側が適用する。呼び出す側はトランポリン上で複数の関数を呼び出せるので、これによって相互再帰を最適化できる。Clojure では、trampoline 関数でこれを実現する。
trampoline 関数
(trampoline f & partial-args)返り値が関数でなければ、trampoline は普通の関数呼び出しと同じである。
(trampoline list) ; ()
(trampoline + 1 2) ; 3しかし、戻り値が関数であると、trampoline はその関数が再帰的に呼び出されることを意図しているとみなし、改めてその関数を呼び出す。trampoline はその中で recur しており、返り値として関数以外のものが返ってくるまで呼び出しを繰り返す。
自己再帰での利用例
たとえば、末尾再帰の節で実装した tail-fibo を改変して、関数を返すようにする。
(defn trampoline-fibo [n]
(let [fib (fn fib [f-2 f-1 current]
(let [f (+ f-2 f-1)]
(if (= n current)
f
#(fib f-1 f (inc current)))))]
(cond
(= n 0) 0
(= n 1) 1
:else (fib 0N 1 2))))この関数を trampoline を使って呼び出す。
(trampoline trampoline-fibo 9) ; 34N大きな値であっても、内部で recur を使っているので、StackOverflowError になることはない。
(rem (trampoline trampoline-fibo 1000000) 1000) ; 875N相互再帰での利用例
自己再帰の場合は trampoline を使う利点はまったくないが、相互再帰では真価を発揮する。例として、相互再帰の節で実装した my-even? と my-odd? に適用する。
(declare my-odd? my-even?)
(defn my-odd? [n]
(if (= n 0)
false
#(my-even? (dec n))))
(defn my-even? [n]
(if (= n 0)
true
#(my-odd? (dec n))))
(trampoline my-even? 1000000) ; trueトランポリンでは、元のコードに手を加えて、再帰する必要があることを呼び出し側に伝える必要がある。他の方法で解決できるに越したことはないが、trampoline を使う方法もあることを覚えておくとよい。
3. 再帰を遅延評価で置き換える
再帰を消したり最適化したりする手段として最もよく使われるのが、遅延評価である。
Eugene Wallingford の replace 関数
例として、相互再帰を示すために Eugene Wallingford が作った replace 関数を実装してみる。
replace は s-list と呼ばれる構造を使う。s-list はシンボルとシンボルのリストの両方を要素にできるリストである。replace は s-list、oldsym、newsym を引数に取り、s-list の中の oldsym をすべて newsym に置き換える。
(replace '((a b) (((b g r) (f r)) c (d e)) b) 'b 'a)
; ((a a) (((a g r) (f r)) c (d e)) a)Clojure で実装する
次はEugene Wallingford の論文の Scheme のコードを、そのまま Clojure へと書き換えたコードである。
(declare replace-symbol replace-symbol-expression)
(defn replace-symbol [coll oldsym newsym]
(if (empty? coll)
()
(cons (replace-symbol-expression
(first coll) oldsym newsym)
(replace-symbol
(rest coll) oldsym newsym))))
(defn replace-symbol-expression [symbol-expr oldsym newsym]
(if (symbol? symbol-expr)
(if (= symbol-expr oldsym)
newsym
symbol-expr)
(replace-symbol symbol-expr oldsym newsym)))2 つの関数 replace-symbol と replace-symbol-expression は相互再帰していて、深くネストした構造を与えると、スタックオーバーフローを起こす可能性がある。
問題を示すために、末尾に 1 つだけ bottom というシンボルを持つ、深くネストしたリストを作る関数を定義する。
(defn deeply-nested [n]
(loop [n n result '(bottom)]
(if (zero? n)
result
(recur (dec n) (list result)))))小さな n に対して、動作を確認してみる。
(deeply-nested 5)
; ((((((bottom))))))
(deeply-nested 25)
; ((((((((((((((((((((((((((bottom))))))))))))))))))))))))))*print-level* でネストした構造を表示する深さを指定する
Clojure には、ネストした構造をどの深さまで表示するかを指定できる *print-level* という変数が用意されている。ネストが指定した深さよりも深いと、print は # で要素を省略して表示する。
(deeply-nested 5)
; ((((((bottom))))))
(deeply-nested 25)
; (((((((((((((((((((((((((#)))))))))))))))))))))))))スタックオーバーフローが起こるのを確認する
replace-symbol を使って、色々な深さにネストしたリストの bottom を deepest に置き換えてみる。
(replace-symbol (deeply-nested 5) 'bottom 'deepest)
; ((((((deepest))))))
(replace-symbol (deeply-nested 10000) 'bottom 'deepest)
; java.lang.StackOverflowError問題を解消する
replace-symbol の再帰呼び出しは、すべて cons の中にある。したがって、再帰を止めるには lazy-seq で包み込むだけでよい。次はClojure らしい書き方になるようにリファクタリングしたコードである。
(defn- coll-or-scalar [x & _] (if (coll? x) :collection :scalar))
(defmulti replace-symbol coll-or-scalar)
(defmethod replace-symbol :collection [coll oldsym newsym]
(lazy-seq
(when (seq coll)
(cons (replace-symbol (first coll) oldsym newsym)
(replace-symbol (rest coll) oldsym newsym)))))
(defmethod replace-symbol :scalar [obj oldsym newsym]
(if (= obj oldsym) newsym obj))lazy-seq で再帰を止めて、深くネストした構造に対するスタックオーバーフローを防ぐ。
また、シンボルとリストをそれぞれ扱う 2 つの関数を定義する代わりに、マルチメソッド replace-symbol を定義して、1 つのメソッドでリストを、もう 1 つでシンボルを扱うようにしている。これにより、if もなくなって読みやすくなる。
実際に深いネストも処理できることを確認する。
(replace-symbol (deeply-nested 10000) 'bottom 'deepest)
; (((((((((((((((((((((((((#)))))))))))))))))))))))))4. メモ化で再帰を止める
より複雑な相互再帰の例として、Douglas Richard Hofstadter の著書『Gödel, Escher, Bach: an Eternal Golden Braid』に登場する Male-Female Sequence について考える。
Male-Female Sequence
このシーケンスは次のように定義される。
この定義をそのまま Clojure に落とし込むと、次のように書ける。
(declare m f)
(defn m [n]
(if (zero? n)
0
(- n (f (m (dec n))))))
(defn f [n]
(if (zero? n)
1
(- n (m (f (dec n))))))この定義は数学的な定義とよく対応しているが、大きな n を計算させようとすると膨大な時間がかかる。
(time (m 250))
; "Elapsed time: 35622.997667 msecs"
; 155シーケンス中の 1 つの値を計算するために 2 つの値を最初から計算する必要があり、そのそれぞれについても 2 つずつの値を最初から計算することになるので、時間がかかる。
メモ化（memoize）
この問題を解決するために、メモ化を使う。
メモ化とは、過去の計算結果をキャッシュして、空間効率と引き換えに時間効率を得る手法である。メモ化された関数は過去に受け取った入力と、その計算結果としての出力とのマップを保持している。呼ばれるとまず与えられた引数でマップを探し、対応する出力が見つかれば直ちに結果を返す。
Clojure では、memoize 関数を使ってこれを実現する。
(def m (memoize m))
(def n (memoize n))これにより、Clojure は F と M の値を各 n について一度ずつ計算すればよいので、性能は飛躍的に向上する。
(time (m 250))
; "Elapsed time: 9.674834 msecs"
; 155さらに、一度メモ化のキャッシュが作られれば、その値を「計算」するのは一瞬である。
(time (m 250))
; "Elapsed time: 0.041458 msecs"
; 155メモ化の問題点
ただし、メモ化だけでは十分でない。メモ化はキャッシュがすでに作られていれば再帰を途中で止められるが、キャッシュが空の状態で大きな数に対する m や f を計算しようとすると、キャッシュが作られる前にスタックオーバーフローが起きる。
(m 10000) ; java.lang.StackOverflowErrorこれを回避するには、関数ではなくシーケンスを定義し、キャッシュが頭から作られるのを保証すればよい。
(def m-seq (map m (iterate inc 0)))
(def n-seq (map m (iterate inc 1)))こうすると、呼び出し側はシーケンスの n 番目の値を nth で取り出して、 や を得られる。
(nth m-seq 250) ; 155このアプローチはn が巨大でもかなり速い。
(time (nth m-seq 10000))
; "Elapsed time: 6462.4185 msecs"
; 6180この節で行ったことを整理する。
- 相互再帰関数を数学的な定義から自然に定義した
- メモ化を使って、すでに計算した分については再帰しないようにした
- シーケンスとして定義して、計算に必要な値が先にキャッシュされるようにした
このアプローチは一度現れた値をすべてキャッシュするので、ヒープ領域を消費する。これが問題になるのであれば、より複雑なキャッシュ方針を選ぶことで解決できることもある。