2010年01月23日

再帰メソッドで、yield returnしたい

   このエントリーをはてなブックマークに追加 Clip to Evernote
再帰メソッドの戻り値を IEnumerable<T>にする場合についてまとめてみました。
順列を列挙するプログラムを例に説明します。
まず、以下のコードを見てください。


このコードの問題点は、_GetPermutations というメソッドの中で、Printメソッドを 呼び出している点です。
これだと、順列を求めるコードと、求めた順列を使って処理をするコードを明確に 分離することができません。
Permutationクラスは、いろんな場面で使える構造になっていないわけです。 問題が異なれば、Printメソッドの部分を書き直さなくてはなりません。

これを解決する方法のひとつが、イベントやdelegateを使う方法です。
順列が求まるたびに、イベントを発行すれば、Permutationクラスの利用者が Permutationクラスに手を入れることなく、自由に独自の処理を書くことができます。

ただ、この方法にも欠点があります。
例えば、GUIのあるプログラムで、次へボタンを押すたびに、順列をひとつずつ表示する ことを考えて見ましょう。こういった要求には、イベント発行する方法は上手く対応する ことができません。

Permutationクラスの利用する側で、Next メソッドなどを使い、ひとつずつ取り出せれば 良いですよね。
それには、Enumerate メソッドの戻り値を、IEnumerable<T>にするのが良さそうです。

以下に、戻り値を、IEnumerable<T> にしたPermutationクラスを示します。


注目すべき点は、再帰メソッドを呼び出して、返ってきた戻り値の扱いです(★印)。
return result とは書けません。
foreachで、一つ一つ要素を取り出し、yield return しています。こうすることで、再帰メソッドで、戻り値をIEnumerable<T>にすることができます。

全ての結果を Listなどに溜め込む方法でも、Enumerateメソッドの戻り値をIEnumerable<T>に出来ますが (この場合は、下請けメソッドの_GetPermutationsの戻り値は、IEnumerable<T>にはなりません)、 全てを列挙し終わらないと、Enumerateメソッドから制御を戻せませんので、 順列の元となる要素数が多い場合には、最初のひとつを取り出すのにも多くの時間を 要してしまい好ましくありません。

では、これを使う側のコードを示します。
まずはforeachで取り出すコード


次に、IEnumerator<T>.MoveNext, IEnumerator<T>.Currentを使うコード


ボタンをクリックするごとに、次の順列を取り出し、labelに表示しています。


 

この記事へのトラックバックURL

http://trackback.blogsys.jp/livedoor/gushwell/51962603