読者です 読者をやめる 読者になる 読者になる

夢とガラクタの集積場

落ちこぼれ三流エンジニアである管理人の夢想=『夢』と、潰えた夢=『ガラクタ』の集積場です。

Clojure勉強日記(その17 より複雑な再帰

こんにちは。

今回は以前試した再帰よりより複雑なケースを用いて再帰を試していく内容のようです。

1.相互再帰

言葉の通り、相互再帰とは2つの関数が互いを呼び合う再帰です。
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

多少時間はかかりますが、応答が返ってきます。
最大無限回数の相互再帰呼び出しが発生する場合、
少し加工するだけでとりあえずエラーがでなくなるため、これも一つの手ではありそうです。

4.再帰を遅延評価で置き換える
5.メモ化で再帰を止める

・・・この2つについてはあまりに扱う問題が個別すぎる状態になるため、今回は見送ります。
Clojureの記述によればいちいち自分で再帰や遅延シーケンスを書かなくても
提供されているライブラリでなんとかなるようですし。

そんなわけで、これは最後に振り返るくらいにして、先に進みます。