まずは問題。
「引数でintの値を1つもらい、1からその値までの和を求めるメソッドを作成せよ」

この問題を見たらまずは以下の処理を思い浮かべるだろう。

手続き型

class MainClass {
        public static void Main(string[] args) {
            Console.WriteLine(SumOf(10));  
        }
        static int SumOf(int n) {
            int sum = 0;
            for(int i = 1; i <= n; i++) {
                sum += i;
            }
            return sum;
        }
}

このソースコードは全く問題ない100点だ。この講座でもまずはこういった処理を繰り返し練習してきた。

関数型プログラミング

ただこのソースコードは以下の本に出てくるプログラミング部の女部長に
「ふん、ださいわね・・・」
とバカにされるコードだ。彼女は以下のようなコードを書く。(本の中では言語はJavaScriptだが)

 class MainClass {
        public static void Main(string[] args) {
            Console.WriteLine(SumOf(10));  
        }

        static int SumOf(int n) {
            return Enumerable.Range(1, n).Sum();
        }
}

関数型プログラミングを使って1から引数までのシーケンスを作ってそれの和を求めるという方法だ。C#ではLINQの機能などを使えば容易にこういったコードもかける。
確かにクールだし素晴らしいと思う。手続き型でだいたいの処理がかけるようになったらこういった関数型アプローチもどんどん取り入れてみるとよいだろう。

再帰

しかし、上記2つの方法以外にも再帰を使って書くこともできる。

class MainClass {
        public static void Main(string[] args) {
            Console.WriteLine(SumOf(10)); 
        }
        static int SumOf(int n) {
            if (n <= 1) {
             return n;
            } else {
             return n + SumOf(n - 1);
            }
        }
    }

誰かが
「再帰処理はロマンだ。」
と言っていたがまさに言い得て妙。
自分自身を再帰的に呼び出しているので処理の流れを追いづらく、またほとんどの場合で速度的に普通のループに劣る。
ただ、再帰がうまくハマったときには思わずニヤリとなる喜びがある。
まさに「ロマン」という言葉がぴったりだろう。

再帰処理の良い例題

再帰処理の数ある例題の中でもっともピッタリとハマっているのが最大公約数を求めるユークリッドの互除法ではないだろうか。

class MainClass {
        public static void Main(string[] args) {
            Console.WriteLine(GCD(824,128)); //->最大公約数は8
        }
        
        static int GCD(int x,int y) {
            if (x%y == 0) {
                return y;
            } else {
                return GCD(y, x % y);
            }
        }
}

ユークリッドの互除法がどういったものなのかはここでは割愛するが再帰処理のハマり具合がいい感じだ。ちなみにループで書いた例が以下

class MainClass {
        public static void Main(string[] args) {
            Console.WriteLine(GCD(824,128)); 
        }
        
        static int GCD(int x,int y) {
            int mod;
            while ((mod = x % y) != 0) {
                x = y;
                y = mod;
            }
            return y;
        }
        
    }

ここではやはり互除法の理屈をそのままメソッドに落とし込んでいる再帰での処理に軍配をあげたい。

再帰のにおい・・・

もちろん再帰はロマンだけではない、普段でも再帰を使ったほうが考えやすい問題もある。
先日、ふとした経緯でとある問題に遭遇した。その問題が以下。

static int[,] data= {
            {0,0,0,0,0,0,0,0,0,0},
            {0,2,2,0,0,0,1,0,3,0},
            {0,2,0,0,0,0,1,0,0,0},
            {0,1,1,0,0,0,1,0,0,0},
            {0,1,1,1,0,1,1,0,1,0},
            {0,0,1,1,1,1,1,1,1,0},
            {0,0,0,1,0,0,0,0,0,0},
        };

「上のような2次元配列で上下左右に連結している同じ数字の個数を返すメソッドを作成せよ。」という問題だ。

例えばインデックスとして1,1を渡すとそこにある数字は2。2が上下左右に連結している数の合計は自分自身を含めると3個だ。

インデックス1,9の場合だとそこにあるのは3。上下左右に隣接している3はないので自分自身のみの1個だ。

ではインデックス4,6の場合は?

ここを指定された場合は?

答えは以下で囲った部分の19となる。

できるかな?

さてこのように指定された場所の隣接した数字の個数を求める処理を作らなければならない。あなたには出来るだろうか?ぜひチャレンジしてもらいたい。
なお、今回この問題はMAXとして100行100列ほどのデータを扱えれば良いものとする。

解答例

話を単純にする

まずは話を単純にしよう。2次元配列だから難しく感じるのだ。まずは1次元に落として考えてみる。

int[] data = {2,4,5,5,3,3,3,3,3,5,3};

このデータであれば隣接した個数を返すというのはそう難しくはないだろう。
例えば、indexとして6を渡すと3の連続している個数5を返すメソッドだ。

あなたも、やってみよう!

ループ

やはり処理としてまずループが思い浮かぶのではないだろうか?

例えば指定されたindexから右方向と左方向をループで調べて違っていたらbreakする以下のようなコードだ。

class MainClass {
        
        public static void Main(string[] args) {
            int[] data = {2,4,5,5,3,3,3,3,3,5,3};
            Console.WriteLine(NumLengthRoop(data, 6));//->5
        }
        static int NumLengthRoop(int[] data,int index) {
            //調べる数値
            int currentNum = data[index];
            //自分自身で1個
            int len = 1;
            //左方向の連続している個数
            for(int i = index-1; i >= 0; i--) {
                if(data[i] != currentNum) {
                    break;
                }
                len++;
            }
            //右方向の連続している個数
            for (int i = index+1; i <data.Length; i++) {
                if (data[i] != currentNum) {
                    break;
                }
                len++;
            }
            return len;
        }
}

これでも全く問題ない。ただここはあえて「再帰」を使って考えてみよう。

非常にしょぼい絵で申し訳ないのだが考え方を説明する。
まず最初に指定されたインデックスが緑で囲まれた3だとする。
そうすると連結された総数は
左方向の結果+1+右方向の結果
となる。

右も左も同じだがここでは右方向を見ていこう。
3かどうかをチェックしてもし3だった場合は
1+右方向の調査結果
を足す。この段階ではまだ確定していないのがポイントだ。

確定していくのは3ではない数字、今回の例でいうと5の場所で初めて0が確定する。
一つが確定すれば後は順番に内側に向かって確定していく。

外から順に確定していき最後に
2+1+2
となって5となる様子がわかっていただけただろうか。

コードで表す。

上の考え方をもとにコードに落としていく。

class MainClass {
        
        public static void Main(string[] args) {
            int[] data = {2,4,5,5,3,3,3,3,3,5,3};
            Console.WriteLine(NumLength(data, 6, data[6], From.START));
        }
       
        //今回考慮すべきは[最初]なのか、[右から]きたのか[左から]きたのかの3種類
        enum From {
            START, RIGHT, LEFT
        }
        //NumLength(調べる配列,調べるindex,現在調べている値,どっちから来たか)
        static int NumLength(int[] data,int index,int currentNum,From from) {
            //もし調べている値とその場所の値が違っていたら
            if (data[index] != currentNum) { 
                return 0;
            } else {
                //自分自身でまず1個
                int len = 1;
                //STARTや右方向から来た場合 かつ 左のインデックスが存在したら
                if (from != From.LEFT && index - 1 >= 0) {
                    //左方向の調査結果をlenに足す。
                    len += NumLength(data, index - 1, currentNum, From.RIGHT);
                }
                //STARTや左から来た場合 かつ 右のインデックスが存在したら
                if (from != From.RIGHT && index+1<data.Length) {
                    //右方向の調査結果をlenに足す。
                    len += NumLength(data, index +1, currentNum, From.LEFT);
                }
                //個数を返す
                return len;
            }
        }
    }

2次元配列で

さていよいよ上の考えを2次元に拡張しよう。まずは簡単な例から

上のように緑で囲まれた1が選択されたとしよう。
考え方は同じだ。
1+上方向+下方向+右方向+左方向
で答えがでる。

どの方向でも同じだが今回も右方向にフォーカスして考えてみよう。

右方向の最初の値は1なので、ここでの値は
1+上方向+右方向+下方向
つまり自分自身の1に来た方向ではない3方向値を足したものとなる。

上方向と下方向は1ではないので0がリターンされてくる。ただ右方向の調査が終わっていないのでここの値はまだ確定しない。

同様に来た方向ではない3方向の調査を進める。

下と右からは0が帰ってくるがやはり上がまだ調査中なのでここも確定しない。

来た方向ではない上、右、左の調査をする。

すべての方向が1ではないので3方向すべてから0が帰ってくる。この部分に関しては調査中がない。値が自分自身のみの1で確定したようだ。

確定した1を呼び出し元に返却。すると下の部分も不確定要素がなくなった。
1と自分自身の1を足してこの部分は2となる。

2を呼び出し元に返却する。するとその部分も不確定要素はなくなり自分自身の1を足して3となる。

呼び出し元に返却しよう。これで右方向は3個だったことがわかった。
この工程を残りの3方向にも行えばよい。

注意点

以上で基本的な考え方は終わりだが2次元になったことによって注意しなければならない点がある。

こういった状況があった場合に呼び出しが永遠に続いてしまう。ただこれの対策は簡単で1度調査した場所は再調査しない仕組みをいれればよい。

完成

以上の考察から導き出されたコードが以下だ。

class MainClass {
        const int MAX = 100;//今回は100行100列ほどあつかえればよい。

        enum From {
            START, TOP, BOTTOM, LEFT, RIGHT
        }
       
        public static void Main(string[] args) {
            
            int[,] data = {
            {0,0,0,0,0,0,0,0,0,0},
            {0,2,2,0,0,0,1,0,3,0},
            {0,2,0,0,0,0,1,0,0,0},
            {0,1,1,0,0,0,1,0,0,0},
            {0,1,1,1,0,1,1,0,1,0},
            {0,0,1,1,1,1,1,1,1,0},
            {0,0,0,1,0,0,0,0,0,0},
            };
            
            //特殊データ(大型データ)
            //int[,] data = new int[MAX, MAX];

            int row = 4;
            int col = 6;
            List<int> list = new List<int>();//調査済みの地点を格納するリスト

            Console.WriteLine(CountLength(data, row, col, data[row, col],From.START,list));

        }

        //上下左右に繋がっている個数を返すメソッド
        static int CountLength(int[,] data, int row, int col, int currentNo, From from,List<int> list) {
            //すでに調査済み地点か数字が違う場合
            if (list.Contains(row * MAX + col) || data[row, col] != currentNo) {
                return 0;
            } else {
                //調査リストに登録(2重カウントの防止)
                //100行100列の場合0~9999が入る可能性がある
                list.Add(row * MAX + col);
                //最低は1(自分自身)
                int len = 1;
                //下方向から来たのでない&&最下行でない
                if (from != From.BOTTOM && row < data.GetLength(0) - 1) {
                    //下方向の調査結果をlenに加える
                    len += CountLength(data, row + 1, col, currentNo, From.TOP,list);
                }
                //上方向から来たのではない&&0行目でない
                if (from != From.TOP && row > 0) {
                    //上方向の調査をlenに加える
                    len += CountLength(data, row - 1, col, currentNo, From.BOTTOM,list);
                }
                //左方向からではない&&一番左の列でない
                if (from != From.LEFT && col > 0) {
                    //左方向の調査をlenに加える
                    len += CountLength(data, row, col - 1, currentNo, From.RIGHT,list);
                }
                //右方向からではない&&一番右の列でない
                if (from != From.RIGHT && col < data.GetLength(1) - 1) {
                    //右方向の調査をlenに加える
                    len += CountLength(data, row, col + 1, currentNo, From.LEFT,list);
                }
                return len;
            }
        }
    }

予想していたよりも記事にするのにかなり多くの時間を費やすことになったが、再帰の面白さやロマンを感じとっていただけたのではないだろうか?
問題解決の一つの手法として再帰を加えるとプログラミングの幅が広がる。
ぜひ色々な局面で試し再帰処理に慣れていってもらいたい。

練習問題

5*5の表を0~9の乱数で埋め以下の処理を実現せよ。
ここでいう接続とは上でやったように上下左右に接続しているもの全てを指す。

[実行例]
 6 7 8 9 4
 9 1 0 0 5
 2 4 5 3 2
 1 1 9 9 9
 4 2 7 1 8
座標をa,bという形式で入力してください(qで終了)>1,1
(1,1)の地点(1)に接続している奇数の合計は17です。
座標をa,bという形式で入力してください(qで終了)>3,2
(3,2)の地点(9)に接続している奇数の合計は45です。
座標をa,bという形式で入力してください(qで終了)>1,2
(1,2)の地点(0)に接続している偶数の合計は8です。
座標をa,bという形式で入力してください(qで終了)>q
終了

解答例

using System;
using System.Collections.Generic;
using System.Linq;
using System.Text;
using System.Threading.Tasks;

namespace ConsoleApp8 {
    class Program {
        const int MAX = 5;//5*5の表
        const int MAX_NUM = 9;//乱数で出す最大値
        public static void Main(string[] args) {
            
            int[,] data = new int[MAX, MAX];
            CreateData(data);
            ShowData(data);
            while (true) {
                Console.Write("座標をa,bという形式で入力してください(qで終了)>");
                string input=Console.ReadLine();
                if (input == "q") {
                    Console.WriteLine("終了");
                    break;
                }
                string[] dataStr = input.Split(',');
                int row = int.Parse(dataStr[0]);
                int col = int.Parse(dataStr[1]);
                var list = new List<int>();
                bool isEven = data[row, col] % 2 == 0;
                int ans = CalcSum(data, row, col,isEven , From.START, list);
                Console.WriteLine($"({row},{col})の地点({data[row,col]})に接続している{(isEven? "偶数":"奇数")}の合計は{ans}です。");
            }
        }
        enum From{
            START,TOP,BOTTOM,RIGHT,LEFT
        }
        static void CreateData(int[,] data) {
            Random rand = new Random();
            for (int i = 0; i < MAX; i++) {
                for (int j = 0; j < MAX; j++) {
                    data[i, j] = rand.Next(MAX_NUM+1);
                }
            }
        }
        static void ShowData(int[,] data) {
            for (int i = 0; i < MAX; i++) {
                for (int j = 0; j < MAX; j++) {
                    Console.Write($"{data[i, j],2}");
                }
                Console.WriteLine();
            }
        }
        static int CalcSum(int[,] data,int row,int col,bool isEven,From from,List<int> list) {
            if(list.Contains(row*MAX+col) || (data[row,col] %2==0) != isEven) {
                return 0;
            } else {
                //調査リストに登録(2重カウントの防止)
                //5行5列の場合0~24が入る可能性がある
                list.Add(row * MAX + col);
                //自分自身の数値
                int sum = data[row,col];
                //下方向から来たのでない&&最下行でない
                if (from != From.BOTTOM && row < data.GetLength(0) - 1) {
                    //下方向の調査結果をlenに加える
                    sum += CalcSum(data, row + 1, col,isEven, From.TOP, list);
                }
                //上方向から来たのではない&&0行目でない
                if (from != From.TOP && row > 0) {
                    //上方向の調査をlenに加える
                    sum += CalcSum(data, row - 1, col, isEven, From.BOTTOM, list);
                }
                //左方向からではない&&一番左の列でない
                if (from != From.LEFT && col > 0) {
                    //左方向の調査をlenに加える
                    sum+= CalcSum(data, row, col - 1, isEven, From.RIGHT, list);
                }
                //右方向からではない&&一番右の列でない
                if (from != From.RIGHT && col < data.GetLength(1) - 1) {
                    //右方向の調査をlenに加える
                    sum += CalcSum(data, row, col + 1, isEven, From.LEFT, list);
                }
                return sum;
            }
        }
    }
}