再帰
再帰とは、関数が自分自身を呼び出すことです。
変ですね――関数がどうやって自分自身を呼び出すんですか？ 無限ループになってしまいませんか？
適切な基本ケースを記述さえすれば、再帰は完璧に機能し、ループでは記述が難しい問題も解決できます。
1. 再帰とは何か？
(1) 1.1 現実世界との類推
| 日常のシーン | 再帰的な機能 |
|---|---|
| 向かい合った2枚の鏡が、互いの姿を映し合っている | 自分自身を呼び出す関数 |
| ロシアのマトリョーシカ（一つ開けると、中にまた一つ入っている） | 問題を、同じ問題のより小さな形に分解すること |
再帰の核心的な考え方： 大きな問題を、直接解けるほど小さくなるまで、同じ問題のより小さなバージョンに分割していくこと。
(2) 1.2 2つの要件
すべての再帰関数には、以下の要素が必須です：
- 基本ケース： 再帰を停止させる条件（最も単純なケース）
- 再帰的なケース： 問題を、それ自体のより小さなバージョンに分解する部分
2. 再帰の例：階乗
(1) 2.1 階乗の定義
TEXT
n! = n × (n-1) × (n-2) × ... × 1
再帰的定義：
TEXT
n! = n × (n-1)! (recursive case)
0! = 1 (base case)
(2) ▶ サンプル：1：再帰を用いた階乗の計算（難易度 ⭐⭐）
CPP
#include iostream
// Recursive function: calculate n!
long long factorial(int n) {
// Base case
if (n == 0) {
return 1;
}
// Recursive case
return n * factorial(n - 1);
}
int main() {
int n;
std::cout << "Enter a non-negative integer: ";
std::cin >> n;
std::cout << n << "! = " << factorial(n) << std::endl;
return 0;
}
実行例：
TEXT
Enter a non-negative integer: 5
5! = 120
(2) 2.2 再帰呼び出しトレース (n=5)
TEXT
factorial(5)
= 5 × factorial(4)
= 5 × 4 × factorial(3)
= 5 × 4 × 3 × factorial(2)
= 5 × 4 × 3 × 2 × factorial(1)
= 5 × 4 × 3 × 2 × 1 × factorial(0)
= 5 × 4 × 3 × 2 × 1 × 1 ← Base case reached, start returning
= 5 × 4 × 3 × 2 × 1
= 5 × 4 × 3 × 2
= 5 × 4 × 6
= 5 × 24
= 120
3. 再帰の例：フィボナッチ数列
(1) 3.1 定義
フィボナッチ数列は 0、1 から始まり、その後の各数は前の 2 つの数の和となります：
TEXT
F(0) = 0 (base case)
F(1) = 1 (base case)
F(n) = F(n-1) + F(n-2) (recursive case, n ≥ 2)
▶ サンプル 2: 再帰を用いたフィボナッチ数列 (難易度 ⭐⭐)
CPP
#include iostream
// Recursive function: calculate the nth Fibonacci number
int fibonacci(int n) {
// Base cases
if (n == 0) return 0;
if (n == 1) return 1;
// Recursive case
return fibonacci(n - 1) + fibonacci(n - 2);
}
int main() {
int n;
std::cout << "Enter n: ";
std::cin >> n;
std::cout << "F(" << n << ") = " << fibonacci(n) << std::endl;
return 0;
}
実行例：
TEXT
Enter n: 10
F(10) = 55
⚠️ 注意： この再帰的なフィボナッチアルゴリズムは、同じ値を何度も再計算してしまうため、n が大きい場合（例えば n > 40 など）には 非常に処理が遅くなります。これは「指数関数的な計算量」と呼ばれます。後で、この問題を解決するための動的計画法について学びます。
4. 再帰とループ
| 側面 | 再帰 | ループ |
|---|---|---|
| コードスタイル | 洗練されていて簡潔 | わかりやすい |
| 読みやすさ | 自然な再帰的な問題に最適 | 単純な繰り返し処理に最適 |
| パフォーマンス | 関数呼び出しによるオーバーヘッド | 高速（呼び出しのオーバーヘッドなし） |
| メモリ | コールスタックを使用する（スタックオーバーフローのリスクあり） | メモリ使用量が少ない |
| 適している用途 | 木構造の探索、分割統治法、バックトラッキング | 単純な反復処理 |
▶ サンプル 3: ループと再帰 — カウントダウン (難易度 ⭐)
ループ版：
CPP
void countDownLoop(int n) {
for (int i = n; i > 0; i--) {
std::cout << i << "... ";
}
std::cout << "Liftoff!" << std::endl;
}
再帰的なバージョン：
CPP
void countDownRecursive(int n) {
if (n == 0) { // Base case
std::cout << "Liftoff!" << std::endl;
return;
}
std::cout << n << "... ";
countDownRecursive(n - 1); // Recursive call
}
💡 ヒント： 再帰的なバージョンはより洗練されていますが、メモリを多く消費します（呼び出しごとにスタックにフレームが追加されるため）。単純な反復処理にはループを使用し、本質的に再帰的な問題（木構造の探索など）には再帰を使用しましょう。
5. 再帰におけるよくある落とし穴
(1) 5.1 基本ケースがない場合 = 無限再帰
CPP
void infiniteRecursion() {
// ❌ No base case! This will run until the stack overflows
std::cout << "Going deeper..." << std::endl;
infiniteRecursion();
}
結果： プログラムは スタックオーバーフロー エラーでクラッシュします。
(2) 5.2 再帰が深すぎる
再帰呼び出しが行われるたびに、スタックメモリが消費されます。再帰が深くなりすぎると（たとえば、10万回の呼び出しなど）、スタックオーバーフローが発生します。
💡 ヒント： 経験則として、再帰の深さが 10,000 を超えるとリスクが高くなります。再帰が非常に深くなる場合は、反復処理による解決策に変換してください。
❓ よくある質問
Q どんなループでも再帰的に書き換えることはできますか？
A はい、どんなループでも再帰的に書き換えることができます。しかし、すべての再帰がループであるべきというわけではありません。木構造の探索など、本来再帰的な性質を持つ問題もあり、それらを反復処理で実装するのははるかに困難です。
Q 再帰とループ、どちらが速いですか？
A ループの方が速いです。関数呼び出しのオーバーヘッドがないからです。しかし、多くの問題（フィボナッチ数列など）では、再帰的な実装の方が理解しやすく、記述も簡単です。パフォーマンスが重要な場合は、後で最適化を行うことができます。
📖 まとめ
- 再帰とは、関数が自分自身を呼び出すことです。これは、同じ問題をより小さな問題に分解して解決することで、大きな問題を解決する手法です。
- すべての再帰関数には、基本ケース（再帰を停止させる）と再帰ケース（自分自身を呼び出す）が必要です。
- 再帰は、本質的に再帰的な問題（階乗、フィボナッチ数列、木構造の探索）に対して洗練された手法である
- ループは一般的に処理が速く、メモリの使用量も少ない
- 注意すべき点：基本ケースの欠落（無限再帰）および再帰の深さ超過（スタックオーバーフロー）
📝 練習問題
-
初心者（難易度 ⭐）： 1 から n までの数の和を返す再帰関数
int sum(int n)を作成してください。n = 100 でテストしてください。 -
中級（難易度 ⭐⭐）： 底^exp を計算する再帰関数
int power(int base, int exp)を作成してください。例えば、power(2, 10)は 1024 を返す必要があります。 -
上級（難易度 ⭐⭐⭐）： ハノイの塔の問題を解く再帰関数を作成してください。各移動を「ディスク1をAからCへ移動」といった形式で出力してください。ディスクの数はユーザーが入力します。
6. 🚀 次は
再帰は強力なツールです。次は、関数のオーバーロード（第13課）について学びます。これは、同じ名前でパラメータが異なる複数の関数を定義する方法です。
