再帰: 自分を呼ぶ関数

マトリョーシカのような構造。アルゴリズムの基礎。

再帰
関数が自分自身を呼び出すこと。
基底条件
再帰呼び出しを止めるための条件分岐。必須。
スタックオーバーフロー
関数呼び出しが深すぎてメモリが枯渇するエラー。
マトリョーシカ (Matryoshka)

再帰関数は「マトリョーシカ人形」です。 人形を開けると、中に一回り小さな同じ人形が入っています（再帰呼び出し）。 これを繰り返していくと、最後には開かない小さな人形（基底条件）が出てきます。 もしこの「最後の小さな人形」が存在しなければ、マトリョーシカは永遠に開き続けられ、部屋が人形で埋め尽くされてしまいます（スタックオーバーフロー）。

再帰の仕組み

関数の中で、自分自身を呼び出すことを「再帰」と呼びます。無限ループに陥らないために、必ず 「基底条件（Base Case）」という停止条件が必要です。

「問題を少しずつ小さくして、解けるサイズまで分割する（分割統治法）」という考え方に基づいています。木構造の探索やソートアルゴリズムなどで威力を発揮します。

再帰の書き方

Factorial Example
// 階乗 (Factorial) の再帰
// n! = n * (n-1)!


int factorial(int n) {
    // 1. 基底条件 (これがないと止まらない)
    if (n <= 1) return 1;


    // 2. 再帰ステップ (問題を小さくして自分を呼ぶ)
    return n * factorial(n - 1);
}


int main(void) {
    printf("%d\n", factorial(5)); // 120
    return 0;
}
Tip: 再帰は「関数呼び出しのスタック」を積み上げます。深すぎるとクラッシュします。

実践テクニック

Stack Overflow

再帰の停止条件を忘れると、メモリ（スタック領域）を使い果たしてプログラムが強制終了します。これが有名なエラー「Stack Overflow」の語源です。

Infinite Recursion
// Stack Overflow の例
void infinite() {
    int a[1000]; // メモリを消費
    printf("Running...\n");
    infinite();  // 自分を呼び続ける
}


// 実行すると...
// セグメンテーション違反 (Segmentation fault)
// スタック領域を使い果たしてクラッシュする

いつ使うべきか

ディレクトリ探索やHTML解析など、「階層の深さがわからないデータ」を扱うときに再帰は最強の武器になります。逆に、単なるループ（1から10まで足すなど）は <code>for</code> 文で書く方が高速で安全です。

演習課題

課題1: カウントダウン
整数 n を受け取り、n, n-1, ... 0 と表示して最後に "Liftoff!" と表示する再帰関数を作成してください。
解答例を見る 
void countdown(int n) {
    if (n == 0) {
        printf("Liftoff!\n");
        return;
    }
    printf("%d\n", n);
    countdown(n - 1);
}

合格ライン

☐ 基底条件（停止条件）を書ける
☐ スタックオーバーフローの原因を説明できる