C# | アルゴリズムと再帰関数 (recursive function)

前半：C#で「アルゴリズム」と「再帰関数」の土台をつくる

C#は型がはっきりしていて、メソッド呼び出しの流れも追いやすいので、再帰を学ぶにはかなり良い言語だと思う。
ここでは、プログラミング初心者でも「再帰の正体」がちゃんと見えるように、アルゴリズムの基礎からゆっくり積み上げていく。

アルゴリズムとは何か

アルゴリズムを日常の言葉にすると

アルゴリズムとは、「問題を解くための手順書」のことだ。
もっとラフに言えば、「こういう順番でやれば必ずゴールにたどり着けるステップの並び」と考えていい。

例えば「インスタントラーメンを作るアルゴリズム」を書くなら、
お湯を沸かす → 麺を入れる → 3分待つ → スープを入れて混ぜる → 器に盛る、
という流れになる。
これをコンピュータが実行できる形にしたものが、プログラムとしてのアルゴリズムだ。

C#でコードを書くというのは、「コンピュータ用の手順書をC#という言語で書く」ことそのものだと思っていい。

なぜアルゴリズムがそんなに大事なのか

文法だけ知っていれば、「とりあえず動くコード」は書ける。
でも現実の開発では、それだけでは足りない。

時間がかかりすぎて実用にならないコード、
メモリを食いすぎて落ちるコード、
入力次第で止まらなくなる危険なコード。

こういうものは、文法的には正しくても「ダメなコード」だ。
アルゴリズムを学ぶというのは、「正しく・速く・安全に」問題を解くための思考を鍛えることだと思ってほしい。
セキュリティの視点でも、アルゴリズム設計が甘いと、DoS（サービス妨害）みたいな脆弱性を自分で仕込むことになる。

再帰関数とは何か（C#版）

一言でいうと「自分自身を呼び出すメソッド」

再帰関数（recursive function）は、「自分の中で自分自身を呼び出すメソッド」のことだ。

static void Foo(int n)
{
    // 何か処理
    Foo(n - 1);  // 自分自身を呼んでいる
}

static void Foo(int n)
{
    // 何か処理
    Foo(n - 1);  // 自分自身を呼んでいる
}

このままだと、永遠に Foo が呼ばれ続けてしまう。
だから再帰には必ず「ここで終わる」という条件が必要になる。

再帰の二本柱：ベースケースと再帰ステップ

再帰メソッドには、必ず二つの要素がセットで存在する。

一つ目がベースケース（基底条件・終わりの条件）。
二つ目が再帰ステップ（問題を少し小さくして自分を呼ぶ部分）。

この二つがそろって初めて、「ちゃんと終わる再帰」になる。
どちらかが欠けると、ほぼ確実にバグか例外か、最悪だと脆弱性になる。

いちばんやさしい再帰：カウントダウンをC#で書く

カウントダウンの再帰メソッド

まずは「n から 1 までカウントダウンして表示する」メソッドを、再帰で書いてみよう。

using System;

class Program
{
    static void Countdown(int n)
    {
        if (n <= 0)                 // ① ベースケース（終わりの条件）
        {
            Console.WriteLine("終了");
            return;
        }

        Console.WriteLine(n);       // ② 今の仕事
        Countdown(n - 1);           // ③ 再帰ステップ（問題を小さくして自分を呼ぶ）
    }

    static void Main()
    {
        Countdown(3);
    }
}

using System;

class Program
{
    static void Countdown(int n)
    {
        if (n <= 0)                 // ① ベースケース（終わりの条件）
        {
            Console.WriteLine("終了");
            return;
        }

        Console.WriteLine(n);       // ② 今の仕事
        Countdown(n - 1);           // ③ 再帰ステップ（問題を小さくして自分を呼ぶ）
    }

    static void Main()
    {
        Countdown(3);
    }
}

実行すると、コンソールには次のように表示される。

3
2
1
終了

ここから、重要な部分を一つずつ深掘りしていく。

ベースケースを深掘りする

if (n <= 0) { ... return; } の部分がベースケースだ。
意味としては、「n が 0 以下になったら、もうこれ以上自分を呼ばずに終わる」という宣言になっている。

もしこの条件がなかったら、Countdown(n - 1) は永遠に呼ばれ続ける。
n は 3 → 2 → 1 → 0 → -1 → -2 → … と減り続け、最終的には C# ランタイムが StackOverflowException を投げてプロセスが落ちる。

セキュリティ・安全性の観点から言うと、「必ず終わる条件を入れる」は再帰の絶対ルールだ。
ここを雑にすると、「特定の入力を与えるとアプリが落ちる」みたいな危険なコードが生まれる。

再帰ステップを深掘りする

Countdown(n - 1); の部分が再帰ステップだ。
ここでやっていることは、「今の n を1つ減らして、残りの仕事を未来の自分に任せる」という動きだ。

Countdown(3) は「3を表示して、あとは Countdown(2) に任せる」。
Countdown(2) は「2を表示して、あとは Countdown(1) に任せる」。
Countdown(1) は「1を表示して、あとは Countdown(0) に任せる」。

そして Countdown(0) でベースケースに到達し、「終了」と表示して終わる。
この「自分は一歩だけ進めて、残りは再帰呼び出しに任せる」という感覚が、再帰のコアにある。

裏側で何が起きているか：コールスタックとC#

コールスタックという舞台裏

C#（というか .NET ランタイム）は、メソッドを呼び出すたびに「どこから呼ばれたか」「そのときのローカル変数の値は何か」といった情報をスタックに積み上げていく。
これを「コールスタック」と呼ぶ。

Countdown(3) の流れを、コールスタックのイメージで追ってみよう。

最初に Countdown(3) が呼ばれる。
その中で Countdown(2) が呼ばれる。
その中で Countdown(1) が呼ばれる。
その中で Countdown(0) が呼ばれる。

このとき、スタックには

Countdown(3)
Countdown(2)
Countdown(1)
Countdown(0)

という感じで「呼び出しの履歴」が積み上がっている。

Countdown(0) がベースケースで return すると、一番上の Countdown(0) がスタックから消える。
次に Countdown(1) に戻り、そこも処理が終わるとスタックから消え…というふうに、一段ずつ戻っていく。
これが「呼び出し元に戻る」という動きの正体だ。

スタックオーバーフローと安全性

再帰が深くなりすぎると、.NET ランタイムは StackOverflowException を投げる。
これは単なる例外ではなく、「入力次第で簡単に落ちるコード」という意味でもある。

特に、ユーザー入力や外部データをそのまま再帰の深さに反映させるようなコードは、セキュリティ的にも慎重に扱うべきだ。
再帰を書くときは、「必ず終わる」「深くなりすぎない」という二つを常に意識する必要がある。

アルゴリズムと再帰の関係

再帰は「アルゴリズムの表現方法」のひとつ

アルゴリズムは「問題を解く手順」だった。
その手順をコードにする方法として、大きく分けて二つある。

一つはループ（for, while）で書く方法。
もう一つは再帰で書く方法。

例えば「1 から n までの合計を求める」というアルゴリズムを考えてみよう。

ループで書く場合

static int SumLoop(int n)
{
    int total = 0;
    for (int i = 1; i <= n; i++)
    {
        total += i;
    }
    return total;
}

static int SumLoop(int n)
{
    int total = 0;
    for (int i = 1; i <= n; i++)
    {
        total += i;
    }
    return total;
}

再帰で書く場合

static int SumRecursive(int n)
{
    if (n == 0)              // ベースケース
    {
        return 0;
    }
    return n + SumRecursive(n - 1);   // 再帰ステップ
}

static int SumRecursive(int n)
{
    if (n == 0)              // ベースケース
    {
        return 0;
    }
    return n + SumRecursive(n - 1);   // 再帰ステップ
}

どちらも「1 から n までの合計を求める」という同じアルゴリズムを実現している。
ただ、表現の仕方が違うだけだ。

再帰は特に、「同じ形の問題を少しずつ小さくしていく」タイプのアルゴリズムを表現するのに向いている。
この「問題を分解する視点」が、アルゴリズムの理解とセキュリティ意識の両方を底上げしてくれる。

前半のまとめと後半へのつなぎ

ここまでの前半で、次の土台をつくった。

アルゴリズムは「問題を解くための手順書」であり、文法とは別に鍛えるべき「考え方」であること。
再帰関数は「自分自身を呼び出すメソッド」だが、本質は「大きな問題を同じ形の小さな問題に分解する」ことにあること。
再帰には「ベースケース」と「再帰ステップ」という二本柱が必須で、これを間違えると StackOverflowException や危険なコードになること。
C#ではコールスタックの上で再帰が動いており、深くなりすぎるとプロセスごと落ちること。
カウントダウンや合計の例で、「自分は一歩だけ進めて、残りは再帰に任せる」という感覚をつかみ始めたこと。

後半では、ここから一歩進んで、
階乗やフィボナッチ数列などの典型的な再帰アルゴリズム、
配列・文字列・木構造を再帰で処理する方法、
再帰とループのどちらを選ぶべきかという判断軸、
再帰を書くときの「思考の型」と、よくある落とし穴、
このあたりをC#コードでしっかり深掘りしていく。