Gushwell's Dev Notes

いげ太さんの記事に触発されて僕も書いてみた。

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

(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

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