Clojure勉強日記（その１７ より複雑な再帰
こんにちは。
今回は以前試した再帰よりより複雑なケースを用いて再帰を試していく内容のようです。
1.相互再帰
言葉の通り、相互再帰とは２つの関数が互いを呼び合う再帰です。
AがAを呼んでそれがAを呼ぶ・・・という形ではなく、AがBを呼び、BがCを呼び、CがAを呼ぶようなコードです。
とりあえず、狙いすぎですが偶数と奇数を判定する関数を作成してお互い呼び出すようにしてみます。
user=> (declare stack-odd? stack-even?) #'user/stack-even? user=> (defn stack-odd? [n] (if (= n 0) false (stack-even? (dec n)))) #'user/stack-odd? user=> (defn stack-even? [n] (if (= n 0) true (stack-odd? (dec n)))) #'user/stack-even? user=> (stack-even? 100) true user=> (stack-odd? 100) false user=> (stack-odd? 101) true
お互いに呼び合って、0になった段階で判定という普通やらないコードですが、
再帰呼び出しという意味ではこの上なくわかりやすいコードです。
当然、何も考えずに再帰呼び出しを行っているため、大きな数を与えるとあふれます。
user=> (stack-odd? 100000) StackOverflowError clojure.lang.Numbers.equal (Numbers.java:214)
この問題への対処として、以下のようなアプローチがあるようです。
実際にこれを試してみます。
2.自己再帰への置き換え
端的に言うと、「相互再帰している時点で関係が深いため、抽象化してまとめて判定できるものに集約する」が対応のようです。
例えば、偶数奇数であればパリティを用いれば偶数は0、奇数は1の値が返るためそれで判定できます。
user=> (defn parity [n] (loop [n n pari 0] (if (= n 0) pari (recur (dec n) (- 1 pari))))) #'user/parity ; 1ずつ減算するごとにparityの値を0と1で往復させ、対象の数が0になったときに値を返す user=> (parity 9) 1 user=> (parity 10) 0
これを使えばevenとodd関数は以下のように書けます。
user=> (defn stack-odd? [n] (= 1 (parity n))) (defn stack-even? [n] (= 0 (parity n))) #'user/stack-odd? user=> #'user/stack-even? user=> (stack-odd? 100000) false user=> (stack-odd? 100001) true
3.トランポリンによる相互再帰
次はトランポリンによる相互再帰・・・です。
トランポリンとは相互再帰を最適化するテクニックだということですが、
Clojureではtrampoline関数で実現されます。
(defn trampoline "trampoline can be used to convert algorithms requiring mutual recursion without stack consumption. Calls f with supplied args, if any. If f returns a fn, calls that fn with no arguments, and continues to repeat, until the return value is not a fn, then returns that non-fn value. Note that if you want to return a fn as a final value, you must wrap it in some data structure and unpack it after trampoline returns." {:added "1.0" :static true} ([f] (let [ret (f)] (if (fn? ret) (recur ret) ret))) ([f & args] (trampoline #(apply f args))))
見た感じ、返り値が関数の場合再帰呼び出し、そうでない場合そのまま返す関数のようですね。
とりあえず普通の値を返す関数を渡して動作を確認してみます。
user=> (trampoline range 10) (0 1 2 3 4 5 6 7 8 9) user=> (trampoline list) ()
部分適用と同じ形で引数を渡す形になりますが、そのまま値が返ってきます。
後は偶数奇数判定関数を「返り値を無名関数を返す」ようにして試してみます。
その上で実行してみると・・・
(defn stack-odd? [n] (if (= n 0) false #(stack-even? (dec n)))) (defn stack-even? [n] (if (= n 0) true #(stack-odd? (dec n)))) user=> (time (trampoline stack-odd? 10000001)) "Elapsed time: 931.528005 msecs" true user=> (time (trampoline stack-even? 10000001)) "Elapsed time: 973.00929 msecs" false
多少時間はかかりますが、応答が返ってきます。
最大無限回数の相互再帰呼び出しが発生する場合、
少し加工するだけでとりあえずエラーがでなくなるため、これも一つの手ではありそうです。
