はじめに

この記事は、初心者プログラマーのための再帰処理の入門記事です。少々回りくどい書き方になってしまいましたが、丁寧な説明を心がけました。

再帰とは

プログラミングでの再帰処理とは、ある処理をするのに、自分自身のメソッドを繰り返し呼び出す処理のことです。

手元の岩波国語辞典で再帰を調べてみると、再帰→回帰とあり、回帰のページには以下のような説明があります。

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

プログラミングでの再帰という用語は、ほぼ本来の意味通りだということが確認できます。

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

簡単な例で考えよう

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

Sum(n) = 1 + 2 + 3 + 4 + ... + (n-2) + (n-1) + n

と表せます。n に具体的な数値を入れてみると、

Sum(1) = 1;
Sum(2) = 1 + 2
Sum(3) = 1 + 2 + 3
Sum(4) = 1 + 2 + 3 + 4
...

となり、変形すると以下のように書き換えることができます。

Sum(1) = 1;
Sum(2) = Sum(1) + 2
Sum(3) = Sum(2) + 3
Sum(4) = Sum(3) + 4
...

これを一般化すると、

Sum(n) = Sum(n-1) + n

と定義できます。

C#で再帰のコード（不完全版）を書いてみる

これが分かれば、再帰コードを書くことが出来ます。

次のようなメソッドをC#で書いてみました。

static int Sum(int n) 
{
    return Sum(n-1) + n;
}

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

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

var n = Sum(5);
Console.WriteLine(n);

static int Sum(int n) 
{
    return Sum(n-1) + n;
}

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

無限再帰を解決して最終的なコードにする

この解決策を提示する前に、ちょっと寄り道して、While 文を使った同様のコードを見てみましょう。

static int SumByWhile(int n)
{
	int result = 0;
	int i = 0;
	while (i < n)
    {	
		result = result + i;
		i++	
    }
	return result;
}

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

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

試しに、

Console.WriteLine(Sum(5));

static int Sum(int n)
{
	Console.Write("{0} ", n);
    // 動きを確認しやすくするためにSleep。
	System.Threading.Thread.Sleep(500);  
	return Sum(n - 1) + n;
}

とし、実行してみましょう。Sum メソッドに渡ってきた引数 n をConsole.Writeで表示するコードと、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;
}

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

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

static int Sum(int n)
{
    if (n == 1)
        return 1;  // 自分自身を呼び出さずに1を返す
    else
        return Sum(n - 1) + n;
}

今風の文法で書けばこんな風にも書けますね。

static int Sum(int n) => n == 1 ? 1 : 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をつかったコードのごちゃごちゃ感がこちらにはありません。

再帰処理のコードはどう動いているのか

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

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

Console.WriteLine(Sum(5));

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) -> 1
Sum(2) -> 3
Sum(3) -> 6
Sum(4) -> 10
15

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

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

最終的に得られた答えが15となります。

おわりに

以上のことからわかるように、C#における再帰呼び出しは、メソッドをどんどん深く呼び出し続けるため、メモリスタックを消費することになります。

大抵の場合はこれでも問題はありませんが、解くべき問題によっては、スタックオーバーが起こりえます。この点は注意が必要です。

しかし、その欠点を補ってあまりあるパワーが再帰にはあります。特に再帰的な構造のデータを処理する際に発揮されます。

最初にあげた、フォルダ構造を扱ったり、家系図のような階層構造(Tree構造）のデータや自己参照構造のリンクリストなどを扱ったりする際にも、再帰はとても有効な手段となります。

ボードゲームのような先読み処理を行う場合にも再帰をよく使います。
また、通常の繰り返し処理やリトライ処理なども再帰で書くことができます。

かなり回りくどい説明になってしまいましたが、再帰処理わかっていただけたでしょうか。

おまけ

ちなみに、僕のQiitaのページでは、再帰を使っているプログラムの記事を沢山載せています。
例えば、

C#で階乗の計算（再帰処理）
C#:全ての要素を使った順列を求める
 C#で再帰メソッドの戻り値を IEnumerable<T>にしたい
 C#:最大公約数を求める（ユークリッドの互除法）
NGraphicsを使ってドラゴン曲線を描く
 C#で数学パズル - 再帰処理で超有名なパズル・ハノイの塔を解いてみた
 C#でパズルを解く - 迷路を深さ優先探索で解く
 C#でパズルを解く - バックトラッキングで8-Queenパズルを解く
 C#でナンプレ(数独)を解くプログラムを書いてみた

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