【プログラミングメモメモ】再帰関数【さいきかんすー】

さいきかんすーとは（不真面目解説）

　前にツイートしたことがあるのですが、その昔僕が悪びれていた頃に、「ブラウザを永遠と起動し続ける」、いわゆる「メモ帳ウイルス」のC言語版を作ることに妙に没頭していました。最初期に作った『「ブラウザを起動」をひたすらwhile(true)でループさせ続ける』というシンプルな構造だと、タスクマネージャでウイルスのタスクを終了されると、すぐ終わってしまうことが欠点でした。

　そこで、発想を変えます。タスクマネージャに捕まらないくらい、すぐに終わらせる方向でアプリを動かしたらどうでしょう。今度はループができなくなりますね。しかし、です。こうすると話は変わります。

　自分はすぐ消えますが、同時に別の自分もブラウザと一緒に開きます。こうすることによってよりタスクマネージャでは消しにくいプログラムが完成したというわけです。

　今回の再帰関数も、実態はこれとあまり変わりません。というのも、「関数（メソッド）の中で自身を呼び出す」という動作を行うことによってより効率的に、よりシンプルにプログラムを書くことができるのです。

　おしまい。

再帰関数とは（真面目解説）

　端的にまとめてしまえば、「関数（メソッド）内で自身（関数）を呼び出す」という仕組みのことを言います。
　あまり長い言葉を書いていると読み手も書き手もわからなくなるので、以下の例を見てください。

　例えば以下の問題を考えます。
（実際のAtCoder問題で、これから先は実際に提出したボクの回答です。正しい方法は別にあるので引用元を参照してください。）

　正の整数 'X' が以下の条件を満たすとき、 'X' はルンルン数であるといいます。
　・'X' を(leading zeroなしで)十進数表記した際に、隣り合うどの2つの桁の値についても、差の絶対値が1以下
　例えば、'1234', '1', '334' などはルンルン数ですが、'31415', '119', '13579' などはルンルン数ではありません。
　正の整数 'K' が与えられます。小さい方から 'K' 番目のルンルン数を求めてください。
（引用元：AtCoder Beginner Contest 161 - D - Lunlun Number）

using System;
using System.Collections.Generic;
using System.Linq;

namespace AtCoderCs
{
   class Program
   {
       static void Main()
       {

           // Num...問題文における 'K' 
           Num = int.Parse(Console.ReadLine());

           // digit...桁数
           var digit = 0;

           // i...カウンター('i == Num' になった時の
           // 'LunLun' 値が計算結果
           i = 0;

           // 'LunLunGetter(int, int)'内で計算を行う
           // 'i == Num' になった時ループを抜けて終了する
           for (; LunLunGetter(digit, -1); digit++) ;


       }

       static int[] LunLun = new int[0];
       static int Num;
       static int i;
       static bool LunLunGetter(int targetDigit, int previousDigit = -1)
       {
           
           // targetDigit...使用する桁数（というか最大インデックス）
           // 実際に使用する桁数は 'targetDigit + 1'
           // previousDigit...ひとつ前の'LunLunGetter'が計算していた数値のある桁数
           // （というかやっぱり0から始まるインデックス）

           // start, end...このメソッドが計算する桁で取りうる値の最小・最大値
           // nowDigit...このメソッドが計算する桁（というかインデックス）

           int start, end;
           var nowDigit = previousDigit + 1;

           // 一桁目（インデックス的には0）から計算する場合
           if (nowDigit == 0)
           {

               // LunLunを初期化しなくちゃいけないから初期化
               LunLun = new int[targetDigit + 1];

               // 一桁目は0以外何でもよいから1以上10未満
               start = 1; end = 10;

           }
           else
           {

               // それ以外は前の桁の数値に依存するからここでswitch
               switch (LunLun[previousDigit])
               {
               case 0:

                   // 0以上2未満
                   start = 0; end = 2;
                   break;
               
               case 9:

                   // 8以上10未満
                   start = 8; end = 10;
                   break;

               default:

                   // その数より1小さい奴以上2大きい奴未満
                   start = LunLun[previousDigit] - 1;
                   end = LunLun[previousDigit] + 2;
                   break;
               }
           }

           // 検証
           for (LunLun[nowDigit] = start; LunLun[nowDigit] < end; LunLun[nowDigit]++)
           {

               // 目的の桁数に達していない場合
               if (targetDigit != nowDigit)
               {

                   // 次の桁を調べる 'LunLunGetter' を呼び出し、その中で値が出力完了した場合は終了する
                   if (!LunLunGetter(targetDigit, nowDigit)) return false;                   
               }
               else
               {

                   // 目的の桁に達した場合
                   // ルンルン数として数える
                   i++;

                   // ルンルン数取得が終了した場合
                   if (i == Num)
                   {

                       LunLun.ToList().ForEach(x => Console.Write(x));
                       return false;

                   }

               }

           }

           return true;

       }

   }
}

　全然、解いている最中は解説にあるような考え方は思い浮かばないし、正直今もあまりうまく理解できていないので、この方法を使わせてください。

　この問題の特徴は、実行結果の桁数がいくつかはわからないところにあります。すると、単純なforでのネストを組むことができません。そこで、再帰関数を使用します。

　初めに、再帰関数に今現在調べようとしている桁数と、ひとつ前に調べた桁数を指定します。その中で、ルンルン数となるために今調べる桁数の数値がとりうる値の範囲を調べてループさせます。
　次の桁数が存在する場合は、次の再帰関数を呼び出すところでループさせると、結果として 'targetDigit + 1' 重ネストみたいな状態になるわけです。

　このように、再帰関数は多重ネストを行うのに便利なパターンですので覚えておきましょう。