再帰の入口——自分を呼ぶ関数

合わせ鏡をのぞくと、鏡の中にまた鏡が映り、その中にもまた鏡が映ります。関数も同じことができます。自分自身を呼び出す関数、それが再帰です。

教科書的な題材は階乗です。5の階乗は 5×4×3×2×1 ですが、これは「5 × 4の階乗」と言い換えられます。同じ形の、少しだけ小さい問題が中に隠れている——この構造が見えたら再帰の出番です。

#include <stdio.h>

int fact(int n)
{
    if (n <= 1) {
        return 1;        // ① 停止条件（ここで止まる）
    }
    return n * fact(n - 1);   // ② 自分を呼ぶ（問題を1つ小さくする）
}

int main(void)
{
    printf("%d\n", fact(5));   // 120
    return 0;
}

再帰に必要な部品は必ずこの2つです。停止条件と、問題が確実に小さくなること。どちらが欠けても止まりません。

中で何が起きているか

fact(3) を呼ぶと、コールスタックにはこう積まれます。

fact(3) … 3 * fact(2) の答え待ち
  fact(2) … 2 * fact(1) の答え待ち
    fact(1) … 1 を返す ← 停止条件

fact(1) が 1 を返すと、fact(2) が 2×1=2 を返し、fact(3) が 3×2=6 を返します。行きは積むだけ、計算は帰り道で起きるのがポイントです。同じ関数でも、呼び出しごとに別のフレームがあるので、n の値はそれぞれ独立しています。

書くときのコツ

再帰を書くときは、途中の動きを全部追いかけようとしないでください。頭が破裂します。確かめるのは次の2点だけです。

1. いちばん小さい場合に正しい答えを返すか（fact(1) は 1 か）
2. fact(n - 1) が正しく動くと仮定したとき、n * fact(n - 1) は正しいか

この2つが言えれば、残りは自動的に正しくなります。数学の帰納法とまったく同じ考え方です。

ループで書くとどうなるか

int fact_loop(int n)
{
    int r = 1;
    for (int i = 2; i <= n; i++) {
        r *= i;
    }
    return r;
}

同じ答えが得られ、しかもこちらのほうが速く、スタックも使いません。階乗のように「1本道の繰り返し」で表せる問題は、実務ではループで書くのがふつうです。それでも再帰を学ぶ価値があるのは、フォルダの中のフォルダをすべてたどる、迷路を分岐ごとに探索する——といった入れ子が自然な問題では、再帰のほうが圧倒的に短く書けるからです。

罠・注意

• 停止条件を書き忘れると無限に積み上がり、スタックオーバーフローでプログラムが落ちます。if (n < 0) return 1; のように、条件はあっても到達しない書き方も同罪です。
• 停止条件があっても、fact(n) の中で fact(n) を呼ぶなど、問題が小さくならなければ止まりません。
• 素朴な再帰は遅いことがあります。フィボナッチ数を fib(n-1) + fib(n-2) で書くと同じ計算を何度も繰り返し、n = 45 あたりで実用に耐えなくなります（第4部で改善策を扱います）。
• 単純な繰り返しはfor文のほうが速く読みやすい場面が多くあります。再帰が輝くのは、木構造の探索のように「入れ子」が自然な問題です。

まとめ: 再帰＝停止条件＋小さくして自分を呼ぶ。行きに積んで帰りに計算する動きをコールスタックで思い描ければ、もう入口は通過です。