再帰の書き方に苦手意識を持つ全ての初心者プログラマを救済すべく書き上げました。
嘘です。苦手意識を持ってたのは私です。
使用環境はC#13.0、.NET 10.0。
もしVisual Studioに「このバージョンでそんな書き方できネーヨ」と怒られた場合、各自で適宜バージョンを落とした書き方を採用してください。IntelliSenseが教えてくれるはずです。
解説
この記事を読むということは最低限の知識はあることでしょう。
再帰の名の通り関数内で自分自身を呼び出すことと、関数内で引数に変化を付けること、終了条件を用意すること。
この三つが分かっていれば大丈夫です。ちゃんと書けます。
関数内で自分自身を呼び出す
C#の言語仕様上、呼び出す関数はその時点で定義済みでなければなりません。
筆者の中で便利と評判のラムダ式を用いた場合ではこんな風には書けません。
// ラムダ式（匿名関数）
var rec = (int i) =>
{
// something to do
return rec(i); // コンパイルエラー。未割り当ての変数。
};
変数を明示的にFunc?型にして一旦nullで初期化することで実行できますが、nullableな警告を何らかの形で抑制する必要があり少々鬱陶しいです。
// null初期化版ラムダ式（匿名関数）
Func<int,int>? rec = null;
rec = (int i) =>
{
// something to do
return rec!(i);
};というわけでここではラムダ式を捨て、ローカル関数を使います。
// ローカル関数
int Rec(int i)
{
// something to do
return Rec(i);
}（staticなど一部を除く）アクセス修飾子が付かず、定義したメソッド内でのみ呼び出せる関数です。
多分これ以外に簡便な実装はないと思います。
引数に変化を付ける
変数に変化を付ける必要があります。
とはいえ目的がないと何をすればいいか分からなくなってしまうので、とりあえず2n乗を計算してみましょう。
nの数だけ2を掛けたいので、その分だけ関数を呼びます。
int Rec(int n)
{
return 2 * Rec(--n);
}終了条件を用意する
このままだと無限ループしてしまうので、終了のための条件を付けます。
int Rec(int n)
{
if (n == 1) return 2;
return 2 * Rec(--n);
}引数に負数や0を渡されると無限ループする問題点は残っていますが、この関数を呼ぶ側の責任として一応は問題なし。これで2nを返す再帰関数が書けました。
後は然るべき時にちゃんと関数を呼び出してあげましょう。(1敗)
Console.WriteLine(Rec(10));
// 1024関数にstatic修飾子を付けない理由
再帰関数の解が1つだけであれば上記の関数で問題ありませんが、解が複数ある問題を再帰によって計算する場合、関数内での結果をListや配列など引数ではない別の変数に格納しておくことがあります。
staticを付けると関数外の変数へのアクセスが不可となるので、どうしてもstaticを使わなくてはならないようなケースでは引数に複数解を格納するための変数を追加するなどという少しキモい（主観）実装になります。
そういった特殊な場合を除けば再帰は動的なローカル関数として実装するほうがコード意図を分かりやすくでき、読みやすい。メンバ変数にアクセスしないとかであればIntelliSenseの言う通りstaticでいいんですけどね。
なぜローカル関数で書くのか
筆者が最初に辿り着けた書き方だから
ローカル関数を書くとして覚えておいたほうが楽です。
再帰処理をクラスのメソッドとして実装する場合、
同一クラス内でも再利用が利きにくい再帰処理を単一メソッド内に隠蔽することでスコープを狭めて意図しない乱用を防止しつつ影響範囲を限定、そのメソッド内で想定しうる例外ケースを弾く前処理を行える。
といったように役割が明確になりやすく一石二鳥。端から、C#で再帰を書く＝ローカル関数を書く、としておけば迷わないですし。
コメント