2011年07月03日

C#プログラマーのための再帰処理・超入門

   このエントリーをはてなブックマークに追加 Clip to Evernote
いげ太さんの記事に触発されて僕も書いてみた。

岩波国語辞典には、再帰→回帰 とあり、回帰の意味を見てみると、

(2) 〔名〕処理手続きや規則の定義に、それ自身を繰り返し使うような仕方。

とあります。
つまり、C#での再帰処理とは、ある処理をするのに、自分自身のメソッドを繰り返し呼び出す処理のことです。

なお、再帰は、処理だけではなく、構造においても使われます。コンピュータのフォルダ構造が
その身近な例ですね。

さて、それでは、1 から n までの整数の合計(これを sum(n)と表す)を求める処理
について考えてみます。


と表せます。

1 から (n-1) までの合計は、というと、sum(n-1) であらわすことができます。

つまり、


と定義できるわけです。
これが、分かれば、再帰コードを書くことが出来ます。

次のようなコードを書いてみました。


何をやっているかと言えば、
Sum(n) を求めるには、Sum(n-1) で自分自身のメソッドを呼び出し、1から n-1 の
合計を求め、その結果に n を加えた値を結果として、返しています。

しかし、これには、大きな欠陥があります。
実際に、動かしてもらえば、分かると思いますが、スタックオーバーフローの例外が発生してしまいます。

なぜならば、Sumメソッドが呼ばれたら、その中で、Sumメソッドを呼び出し、さらに、
その中で、Sumメソッドを呼び出し.... を繰り返すわけですから、無限に、Sum を呼び
続けてしまうわけです。

さて、ここで、While 文を使った、同様のコードを見てみましょう。


このコードでは、無限ループにならないように、i < n でループの終了判定を行っていますね。

再帰のコードも同様に、再帰の終了判定を行わないと、無限にメソッドを呼び続ける
ことになるのです。

ためしに、


とし、実行してみましょう。Sum メソッドに渡ってきた 引数 n をConsole.WriteLineで
表示するコードと、Sleepメソッドを追加しています。

※ 途中で、Ctrl+Cを押して、プログラムを終了させてください。


と表示され、Sumの引数に 0 以下の値が渡ってきていることが確認できます。
これを見れば、1 がきたところで、再帰呼び出しをストップすれば良いことがわかります。

それでは、再帰版のSumメソッドに終了判定を入れたいと思います。


※ 一時変数の resultは取り除いています。

問題は、コメントにも書いたように、n が 1の時に何を書くかです。

具体的に、Sum(1) の結果が何かを考えてみると、1 が返ればよいわけですから、
最終的なコードは、次のようになります。

なお、最初に、Sum(n)は、


と定義できると書きましたが、これはより正確には、


となります。
この定義をそのまま、C#のコードに書き下したものが、上記Sumメソッドとなります。
これは、メソッドの定義が、手続き的な「処理の記述」から、問題の構造そのものを表す
「問題の定義」に近くなっていることを示しています。(言い換えると、HowからWhatですね)
コード自体も、とてもすっきりしていますね。whileをつかったコードのごちゃごちゃ感が
こちらにはありません。

ただ、手続きを書くことに慣れているプログラマーには、これでは、どう動くのかが
良くわからないという方も多いと思います。実際に、僕が若いころに再帰を学んだ時はそうでした。

ということで、どう動いているのかを確認してみましょう。
以下のようにデバッグ行を追加してみます。


この結果は、
となります。
これを言葉で言い換えると、次のようになるかと思います。


1. Sum(5)を求めるには、そのひとつ前のSum(4)を知らなければならない、だからSum(4)を呼ぶ。
2. Sum(4)を求めるには、そのひとつ前のSum(3)を知らなければならない、だからSum(3)を呼ぶ。
3. Sum(3)を求めるには、そのひとつ前のSum(2)を知らなければならない、だからSum(2)を呼ぶ。
4. Sum(2)を求めるには、そのひとつ前のSum(1)を知らなければならない、だからSum(1)を呼ぶ。
5. Sum(1) は、1だから、1 を返す。
6. Sum(1)が求まったから、Sum(2) は、Sum(1) + 2 で 1 + 2 になるので、3を返す。
7. Sum(2)が求まったから、Sum(3) は、Sum(2) + 3 で 3 + 3 になるので、6を返す。
8. Sum(3)が求まったから、Sum(4) は、Sum(3) + 4 で 6 + 4 になるので、10を返す。
9. Sum(4)が求まったから、Sum(5) は、Sum(4) + 5 で 10 + 5 になるので、15を返す。


これからわかるように、C#における再帰呼び出しは、メソッドをどんどん深く呼び出し続けるため、
スタックを消費することになります。
大抵の場合は、これでも問題はありませんが、解くべき問題によっては、スタックオーバーが
起こりえます。この点は注意が必要です。

しかし、その欠点を補ってあまりあるパワーが再帰にはあります。
それは、再帰的な構造のデータを処理する際に、発揮されます。
先ほどあげた、フォルダ構造を扱ったり、家系図のような階層構造(Tree構造)のデータを扱う際には、
再帰はとても有効な手段となります。

ボードゲームのような先読みを処理を行うにも、再帰は有効(というか必須)です。
また、リンクリストを扱ったり、今回のような通常の繰り返し処理や、リトライ処理などでも
再帰が使えますね。

なお、いげ太さんの記事では、末尾再帰によるコードが示されていますが、
C#のコンパイラには、末尾再帰の最適化が組み込まれていません。 そのために、ここでは、末尾再帰のコードは示していません。
末尾再帰について知りたければ、こことかここを見てください。



ちなみに、僕のWebサイト「Gushwell"s C# Programming Page」の「C# プログラム小品集」
に掲載したプログラムでも、再帰を使っているプログラムがたくさんあります。
例えば、

階乗の計算
http://gushwell.ifdef.jp/etude/Factorial.html

すべての順列を求める
http://gushwell.ifdef.jp/etude/Permutation.html

ヒルベルト曲線
http://gushwell.ifdef.jp/etude/HirbertCurve.html

8-Queenパズル
http://gushwell.ifdef.jp/etude/nQueen.html

最大面積の領域を求める
http://gushwell.ifdef.jp/etude/MaxArea.html

などです。興味がありましたら、読んでみてください。



 

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

http://trackback.blogsys.jp/livedoor/gushwell/52169579
この記事へのトラックバック
素敵なエントリーの登録ありがとうございます - .NET Clipsからのトラックバック
C#プログラマーのための再帰処理・超入門:Gushwell's C# Dev Notes【.NET Clips】at 2011年07月05日 22:42