C++: 再帰
最終更新：2026-08-31
再帰は自分自身を呼び出す関数——複雑な問題をより小さな同じ問題に分割する強力なテクニック。理解すれば簡単だが、最初は難しい。このレッスンでは、再帰がどう動くか、いつ使うかを学ぶ。
1. 再帰とは何か？
(1) 1.1 定義
再帰は、自分自身を呼び出す関数。
(2) 1.2 現実の例え
| 再帰的シナリオ | プログラミングでの相当 |
|---|---|
| 辞書で「再帰」を調べる | 「自分自身を呼び出す関数」 |
| 「巨大な箱の中に箱がある。その中に箱がある。一番小さな箱を見つけるまで」 | 各箱を開く = 再帰呼び出し |
| 鏡が鏡を映す | 無限の反射（基底ケースなし） |
2. 再帰の解剖
すべての再帰関数には2つの部分がある：
(1) 2.1 基底ケース
再帰を停止する条件。これがないと、関数は永遠に呼び出し続け、スタックオーバーフローでクラッシュする。
(2) 2.2 再帰ケース
関数が自分自身を呼び出す部分。各呼び出しは基底ケースに近づかなければならない。
▶ サンプル 1：階乗（難易度 ⭐）
CPP
#include <iostream>
int factorial(int n) {
// 基底ケース
if (n <= 1) {
return 1;
}
// 再帰ケース
return n * factorial(n - 1);
}
int main() {
std::cout << "5! = " << factorial(5) << std::endl;
std::cout << "0! = " << factorial(0) << std::endl;
return 0;
}
出力：
TEXT
📖 参照専用
5! = 120
0! = 1
3. コールスタック
(1) 3.1 仕組み
各関数呼び出しはスタックフレーム（パラメータとローカル変数を含む）をメモリスタックにプッシュする。
TEXT
📖 参照専用
factorial(5) → 5 * factorial(4)
factorial(4) → 4 * factorial(3)
factorial(3) → 3 * factorial(2)
factorial(2) → 2 * factorial(1)
factorial(1) → 1 (基底ケース！)
戻り：
TEXT
📖 参照専用
factorial(1) = 1
factorial(2) = 2 * 1 = 2
factorial(3) = 3 * 2 = 6
factorial(4) = 4 * 6 = 24
factorial(5) = 5 * 24 = 120
4. 再帰 vs 反復
| 再帰 | 反復 |
|---|---|
| コードがシンプル | パフォーマンスが良い |
| スタックオーバーフローのリスク | メモリ効率が良い |
| 問題によっては自然（木、グラフ） | すべてに適用可能 |
| 関数呼び出しのオーバーヘッド | ループのみ |
▶ サンプル 2：フィボナッチ（難易度 ⭐⭐）
CPP
#include <iostream>
int fibonacci(int n) {
if (n <= 0) return 0; // 基底ケース 1
if (n == 1) return 1; // 基底ケース 2
return fibonacci(n - 1) + fibonacci(n - 2); // 再帰ケース
}
int main() {
for (int i = 0; i <= 10; i++) {
std::cout << "fib(" << i << ") = " << fibonacci(i) << std::endl;
}
return 0;
}
出力：
TEXT
📖 参照専用
fib(0) = 0
fib(1) = 1
fib(2) = 1
fib(3) = 2
fib(4) = 3
fib(5) = 5
fib(6) = 8
fib(7) = 13
fib(8) = 21
fib(9) = 34
fib(10) = 55
5. よくある間違い
(1) 5.1 基底ケースの忘れ
TEXT
📖 参照専用
int bad(int n) {
return n + bad(n - 1); // ❌ 基底ケースなし = 無限再帰 = クラッシュ
}
(2) 5.2 基底ケースに近づかない
CPP
int bad(int n) {
if (n == 0) return 0;
return n + bad(n + 1); // ❌ nが増える！基底ケースから遠ざかる
}
6. 再帰が適している場合
- 木の走査（ファイルシステム、DOM）
- グラフアルゴリズム（DFS、バックトラッキング）
- 分割統治（マージソート、クイックソート）
- 数列生成
- 構文解析（数式、JSON）
▶ サンプル 3：数字の桁数を再帰で計算（難易度 ⭐）
CPP
#include <iostream>
int countDigits(int n) {
if (n < 0) n = -n; // 負の数を正に
if (n < 10) return 1; // 基底ケース: 1桁
return 1 + countDigits(n / 10); // 再帰ケース
}
int main() {
std::cout << "12345の桁数: " << countDigits(12345) << std::endl;
std::cout << "7の桁数: " << countDigits(7) << std::endl;
std::cout << "-987の桁数: " << countDigits(-987) << std::endl;
return 0;
}
❓ よくある質問
Q なぜ再帰はスタックオーバーフローを起こす？
A 各関数呼び出しがスタックメモリを使う。基底ケースなしで無限に呼び出すと、スタックが満杯になりクラッシュ。
Q いつ再帰を使い、いつループを使う？
A 問題が自然に再帰的（木、グラフ）なら再帰。単純な繰り返しなら反復。迷ったら反復——パフォーマンスが良い。
Q 末尾再帰とは？
A 再帰呼び出しが関数の最後にある場合、コンパイラがループに最適化できる。C++はこれを保証しないが、良いプラクティス。
📖 まとめ
- 再帰は自分自身を呼び出す関数
- すべての再帰には基底ケース（停止条件）が必要
- 再帰は問題をより小さな同じ問題に分割
- コールスタックが関数呼び出しを追跡
- 再帰はコードをシンプルにできるが、パフォーマンスコストがある
📝 練習問題
-
初級（難易度 ⭐）：
int sum(int n)を書き、1からnまでの和を再帰で計算。 -
中級（難易度 ⭐⭐）：
int power(int base, int exp)を書き、base^expを再帰で計算。 -
上級（難易度 ⭐⭐⭐）：
bool isPalindrome(std::string s)を再帰で書き、文字列が回文かチェック。
