再帰関数とは

再帰関数とは 自分自身を呼び出す関数 のことです
同じ処理構造を「少しずつ小さな問題に分けながら解く」ときに使われます

数学の 階乗（n!） を例にすると

n! = n × (n-1)!

のように「同じ形の式が繰り返し現れる」という特徴があります
このような処理をプログラムで自然に表現できるのが再帰関数です

再帰関数の基本構造

再帰関数には 絶対に守るべきポイントが2つ あります

１．自分自身を呼び出す処理がある

関数の中で、その関数自身を呼び出します

２．終了条件（ベースケース）が必ず必要

ある条件になったら「これ以上呼び出さずに値を返す」という終了条件が必要です
これがないと

・処理が永遠に続く
・スタックオーバーフローでクラッシュ

という事故が起きます

サンプル：階乗を再帰関数で計算する

#include <stdio.h>

// 再帰関数の定義
int factorial(int n) {
    if (n == 0) {   // 終了条件
        return 1;
    } else {
        return n * factorial(n - 1);  // 自分自身を呼び出す
    }
}

int main(void) {
    int num = 5;
    int result = factorial(num);

    printf("%d! = %d\n", num, result);

    return 0;
}

/* 出力結果
5! = 120
*/

処理の流れを分解して見る

再帰は「頭の中で追いにくい」のが最大の壁なのでここは丁寧に説明すると有用性が上がる

factorial(5)
→ 5 × factorial(4)
→ 4 × factorial(3)
→ 3 × factorial(2)
→ 2 × factorial(1)
→ 1 × factorial(0)
→ 1（終了条件）

ここで初めて処理が止まり

1 × 1 × 2 × 3 × 4 × 5 = 120

と 呼び出しが巻き戻るように計算結果が返ってくる
この「積み上がってから戻る」感覚が再帰関数を理解する最大のポイント

再帰関数が向いている場面

再帰は万能ではなく「向いている処理」がはっきりしています

再帰が向いている例

・階乗やフィボナッチ数列などの数学的定義
・木構造の処理（ディレクトリ、構文木など）
・分割して解くアルゴリズム

• クイックソート
• マージソート

「同じ処理を小さく分けて繰り返す」という構造のときに強いです

再帰関数の注意点

終了条件は必ず書く

これがない再帰関数は 必ず暴走します

呼び出しが深すぎると危険

再帰は呼び出すたびにスタック領域を消費します

• 深い再帰
• 終了条件が遅い

この2つが重なると スタックオーバーフロー が発生します

単純な繰り返しならループの方が良い

例えば階乗は

int fact = 1;
for (int i = 1; i <= n; i++) {
    fact *= i;
}

の方が

• 速い
• メモリ効率が良い
• 読みやすい

ことが多いです

再帰とループの使い分けの考え方

• 処理が単純な繰り返し → for / while
• 構造が入れ子・分割型 → 再帰
• 深さが不明 or 深くなりそう → ループ

「再帰が書ける」ことより
「再帰を使うべきか判断できる」ことの方が重要

まとめ

• 再帰関数は自分自身を呼び出す関数
• 必ず終了条件（ベースケース）が必要
• 処理は呼び出されてから戻るときに計算される
• 木構造や分割型の処理に向いている
• 単純な繰り返しはループの方が安全で高速