合わせ鏡をのぞくと、鏡の中にまた鏡が映り、その中にもまた鏡が映ります。関数も同じことができます。自分自身を呼び出す関数、それが再帰です。
教科書的な題材は階乗です。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点だけです。
- いちばん小さい場合に正しい答えを返すか（
fact(1)は 1 か） 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文のほうが速く読みやすい場面が多くあります。再帰が輝くのは、木構造の探索のように「入れ子」が自然な問題です。
まとめ: 再帰＝停止条件＋小さくして自分を呼ぶ。行きに積んで帰りに計算する動きをコールスタックで思い描ければ、もう入口は通過です。