2011年07月03日
C#プログラマーのための再帰処理・超入門
いげ太さんの記事に触発されて僕も書いてみた。
岩波国語辞典には、再帰→回帰 とあり、回帰の意味を見てみると、
とあります。
つまり、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 が返ればよいわけですから、
最終的なコードは、次のようになります。
と定義できると書きましたが、これはより正確には、
となります。
この定義をそのまま、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
などです。興味がありましたら、読んでみてください。
岩波国語辞典には、再帰→回帰 とあり、回帰の意味を見てみると、
(2) 〔名〕処理手続きや規則の定義に、それ自身を繰り返し使うような仕方。
とあります。
つまり、C#での再帰処理とは、ある処理をするのに、自分自身のメソッドを繰り返し呼び出す処理のことです。
なお、再帰は、処理だけではなく、構造においても使われます。コンピュータのフォルダ構造が
その身近な例ですね。
さて、それでは、1 から n までの整数の合計(これを sum(n)と表す)を求める処理
について考えてみます。
sum(n) = 1 + 2 + 3 + 4 + ... + (n-2) + (n-1) + n
と表せます。
1 から (n-1) までの合計は、というと、sum(n-1) であらわすことができます。
つまり、
sum(n) = sum(n-1) + n
と定義できるわけです。
これが、分かれば、再帰コードを書くことが出来ます。
次のようなコードを書いてみました。
int Sum(int n) {
int result = Sum(n-1) + n;
return result;
}
何をやっているかと言えば、
Sum(n) を求めるには、Sum(n-1) で自分自身のメソッドを呼び出し、1から n-1 の
合計を求め、その結果に n を加えた値を結果として、返しています。
しかし、これには、大きな欠陥があります。
実際に、動かしてもらえば、分かると思いますが、スタックオーバーフローの例外が発生してしまいます。
なぜならば、Sumメソッドが呼ばれたら、その中で、Sumメソッドを呼び出し、さらに、
その中で、Sumメソッドを呼び出し.... を繰り返すわけですから、無限に、Sum を呼び
続けてしまうわけです。
さて、ここで、While 文を使った、同様のコードを見てみましょう。
static int WhileSum(int n) {
int result = 0;
int i = 0;
while (i < n) {
result = result + i;
i++;
}
return result;
}
このコードでは、無限ループにならないように、i < n でループの終了判定を行っていますね。
再帰のコードも同様に、再帰の終了判定を行わないと、無限にメソッドを呼び続ける
ことになるのです。
ためしに、
class Program {
static void Main(string[] args) {
Console.WriteLine(Sum(5));
}
static int Sum(int n) {
Console.Write("{0} ", n);
System.Threading.Thread.Sleep(100);
int result = Sum(n - 1) + n;
return result;
}
}
とし、実行してみましょう。Sum メソッドに渡ってきた 引数 n をConsole.WriteLineで
表示するコードと、Sleepメソッドを追加しています。
※ 途中で、Ctrl+Cを押して、プログラムを終了させてください。
5 4 3 2 1 0 - 1 - 2 -3 ...
と表示され、Sumの引数に 0 以下の値が渡ってきていることが確認できます。
これを見れば、1 がきたところで、再帰呼び出しをストップすれば良いことがわかります。
それでは、再帰版のSumメソッドに終了判定を入れたいと思います。
static int Sum(int n) {
if (n == 1)
; // ここに何を書く?
else
return Sum(n - 1) + n;
}
※ 一時変数の resultは取り除いています。
問題は、コメントにも書いたように、n が 1の時に何を書くかです。
具体的に、Sum(1) の結果が何かを考えてみると、1 が返ればよいわけですから、
最終的なコードは、次のようになります。
static int Sum(int n) {
if (n == 1)
return 1;
else
return Sum(n - 1) + n;
}
なお、最初に、Sum(n)は、sum(n) = sum(n-1) + n
と定義できると書きましたが、これはより正確には、
n == 1 の時
Sum(n) = 1
n > 1 の時
Sum(n) = Sum(n-1) + n
となります。
この定義をそのまま、C#のコードに書き下したものが、上記Sumメソッドとなります。
これは、メソッドの定義が、手続き的な「処理の記述」から、問題の構造そのものを表す
「問題の定義」に近くなっていることを示しています。(言い換えると、HowからWhatですね)
コード自体も、とてもすっきりしていますね。whileをつかったコードのごちゃごちゃ感が
こちらにはありません。
ただ、手続きを書くことに慣れているプログラマーには、これでは、どう動くのかが
良くわからないという方も多いと思います。実際に、僕が若いころに再帰を学んだ時はそうでした。
ということで、どう動いているのかを確認してみましょう。
以下のようにデバッグ行を追加してみます。
static void Main(string[] args) {
Console.WriteLine(Sum(5));
Console.ReadLine();
}
static int Sum(int n) {
Console.WriteLine("Sum({0}) called", n);
if (n == 1) {
return 1;
} else {
int a = Sum(n - 1);
Console.WriteLine("Sum({0}) -> {1}", n - 1, a);
return a + n;
}
}
この結果は、
Sum(5) called Sum(4) called Sum(3) called Sum(2) called Sum(1) called Sum(1) return 1 Sum(2) return 3 Sum(3) return 6 Sum(4) return 10 Sum(5) return 15 15となります。
これを言葉で言い換えると、次のようになるかと思います。
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
などです。興味がありましたら、読んでみてください。
Posted by gushwell at 23:00│Comments(2)
この記事へのコメント
文頭の「いげ太さんの記事」がリンク切れしています。
この記事でしょうか?
http://www.atmarkit.co.jp/fdotnet/chushin/greatblogentry_03/greatblogentry_03_01.html
この記事でしょうか?
http://www.atmarkit.co.jp/fdotnet/chushin/greatblogentry_03/greatblogentry_03_01.html
Posted by
kukekko at
2017年08月17日 09:49
kukekkoさん
ご指摘の通り、その記事です。
元記事である「いげ太さんのブログ」へリンクを貼っていたのですが、ブログが閉鎖されてしまったようですね。それでリンク切れになっていたようです。
@ITへの記事へのリンクに張り替えました。
どうもありがとうございました。
ご指摘の通り、その記事です。
元記事である「いげ太さんのブログ」へリンクを貼っていたのですが、ブログが閉鎖されてしまったようですね。それでリンク切れになっていたようです。
@ITへの記事へのリンクに張り替えました。
どうもありがとうございました。
Posted by gushwell at
2017年08月17日 22:45
この記事へのトラックバック
素敵なエントリーの登録ありがとうございます - .NET Clipsからのトラックバック
C#プログラマーのための再帰処理・超入門:Gushwell's C# Dev Notes【.NET Clips】at 2011年07月05日 22:42