Day 5: 再帰と分割統治法
今日学ぶこと
- 再帰の基本概念とコールスタック
- 基底条件と再帰条件
- 分割統治法の考え方
- 再帰を使った実践的なアルゴリズム
再帰とは
再帰（Recursion） とは、関数が自分自身を呼び出すことです。大きな問題を同じ構造の小さな問題に分解して解きます。
flowchart TB
subgraph Recursion["再帰の流れ"]
F5["factorial(5)"] --> F4["5 × factorial(4)"]
F4 --> F3["4 × factorial(3)"]
F3 --> F2["3 × factorial(2)"]
F2 --> F1["2 × factorial(1)"]
F1 --> BASE["1（基底条件）"]
end
style Recursion fill:#3b82f6,color:#fff
style BASE fill:#22c55e,color:#fff
function factorial(n) {
// Base case
if (n <= 1) return 1;
// Recursive case
return n * factorial(n - 1);
}
console.log(factorial(5)); // 120 (5 × 4 × 3 × 2 × 1)
再帰の2つの要素
すべての再帰関数には次の2つが必要です：
1. 基底条件（Base Case）
再帰を停止する条件です。これがないと無限ループになります。
2. 再帰条件（Recursive Case）
問題を小さくして自分自身を呼び出す部分です。
function countdown(n) {
// Base case
if (n <= 0) {
console.log("Done!");
return;
}
// Recursive case
console.log(n);
countdown(n - 1);
}
countdown(5); // 5, 4, 3, 2, 1, Done!
コールスタック
再帰呼び出しはコールスタックに積まれます。基底条件に達すると、逆順に戻り値が返されます。
flowchart TB
subgraph CallStack["コールスタック"]
direction TB
S1["factorial(1) → 1"]
S2["factorial(2) → 2 × 1"]
S3["factorial(3) → 3 × 2"]
S4["factorial(4) → 4 × 6"]
S5["factorial(5) → 5 × 24"]
end
S5 --> S4 --> S3 --> S2 --> S1
S1 -.->|return 1| S2
S2 -.->|return 2| S3
S3 -.->|return 6| S4
S4 -.->|return 24| S5
style CallStack fill:#8b5cf6,color:#fff
スタックオーバーフロー
再帰が深すぎるとスタックオーバーフローが発生します。
// This will crash!
function infinite() {
return infinite(); // No base case
}
// RangeError: Maximum call stack size exceeded
再帰の基本パターン
配列の合計
function sum(arr) {
if (arr.length === 0) return 0;
return arr[0] + sum(arr.slice(1));
}
console.log(sum([1, 2, 3, 4, 5])); // 15
配列の反転
function reverse(str) {
if (str.length <= 1) return str;
return reverse(str.slice(1)) + str[0];
}
console.log(reverse("hello")); // "olleh"
べき乗の計算
// O(n) version
function power(base, exp) {
if (exp === 0) return 1;
return base * power(base, exp - 1);
}
// O(log n) version using divide and conquer
function fastPower(base, exp) {
if (exp === 0) return 1;
if (exp % 2 === 0) {
const half = fastPower(base, exp / 2);
return half * half;
}
return base * fastPower(base, exp - 1);
}
console.log(fastPower(2, 10)); // 1024
分割統治法（Divide and Conquer）
分割統治法は、問題を以下の3つのステップで解きます：
flowchart TB
P["問題"] --> D["1. 分割（Divide）\n問題を小さく分ける"]
D --> C["2. 統治（Conquer）\n各部分を再帰的に解く"]
C --> M["3. 結合（Combine）\n結果を合わせる"]
style P fill:#3b82f6,color:#fff
style D fill:#22c55e,color:#fff
style C fill:#f59e0b,color:#fff
style M fill:#8b5cf6,color:#fff
例：マージソート
function mergeSort(arr) {
// Base case
if (arr.length <= 1) return arr;
// Divide
const mid = Math.floor(arr.length / 2);
const left = arr.slice(0, mid);
const right = arr.slice(mid);
// Conquer
const sortedLeft = mergeSort(left);
const sortedRight = mergeSort(right);
// Combine
return merge(sortedLeft, sortedRight);
}
function merge(left, right) {
const result = [];
let i = 0, j = 0;
while (i < left.length && j < right.length) {
if (left[i] <= right[j]) {
result.push(left[i++]);
} else {
result.push(right[j++]);
}
}
return [...result, ...left.slice(i), ...right.slice(j)];
}
console.log(mergeSort([38, 27, 43, 3, 9, 82, 10]));
// [3, 9, 10, 27, 38, 43, 82]
flowchart TB
A["[38, 27, 43, 3, 9, 82, 10]"] --> B["[38, 27, 43]"]
A --> C["[3, 9, 82, 10]"]
B --> D["[38]"]
B --> E["[27, 43]"]
E --> F["[27]"]
E --> G["[43]"]
C --> H["[3, 9]"]
C --> I["[82, 10]"]
H --> J["[3]"]
H --> K["[9]"]
I --> L["[82]"]
I --> M["[10]"]
F -.-> N["[27, 43]"]
G -.-> N
D -.-> O["[27, 38, 43]"]
N -.-> O
J -.-> P["[3, 9]"]
K -.-> P
L -.-> Q["[10, 82]"]
M -.-> Q
P -.-> R["[3, 9, 10, 82]"]
Q -.-> R
O -.-> S["[3, 9, 10, 27, 38, 43, 82]"]
R -.-> S
style A fill:#3b82f6,color:#fff
style S fill:#22c55e,color:#fff
二分探索（分割統治法の例）
function binarySearch(arr, target, left = 0, right = arr.length - 1) {
// Base case
if (left > right) return -1;
// Divide
const mid = Math.floor((left + right) / 2);
// Conquer
if (arr[mid] === target) return mid;
if (arr[mid] < target) {
return binarySearch(arr, target, mid + 1, right);
}
return binarySearch(arr, target, left, mid - 1);
}
const sorted = [1, 3, 5, 7, 9, 11, 13, 15];
console.log(binarySearch(sorted, 7)); // 3
console.log(binarySearch(sorted, 6)); // -1
再帰 vs 反復
すべての再帰は反復（ループ）に書き換えることができます。
// Recursive fibonacci: O(2ⁿ)
function fibRecursive(n) {
if (n <= 1) return n;
return fibRecursive(n - 1) + fibRecursive(n - 2);
}
// Iterative fibonacci: O(n)
function fibIterative(n) {
if (n <= 1) return n;
let prev = 0, curr = 1;
for (let i = 2; i <= n; i++) {
[prev, curr] = [curr, prev + curr];
}
return curr;
}
// Memoized fibonacci: O(n)
function fibMemo(n, memo = {}) {
if (n <= 1) return n;
if (memo[n]) return memo[n];
memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
return memo[n];
}
| 方法 | 時間計算量 | 空間計算量 |
|---|---|---|
| 素朴な再帰 | O(2ⁿ) | O(n) |
| メモ化再帰 | O(n) | O(n) |
| 反復 | O(n) | O(1) |
末尾再帰
末尾再帰は、再帰呼び出しが関数の最後の操作である場合です。一部の言語ではコンパイラが最適化できます。
// Not tail recursive
function factorial(n) {
if (n <= 1) return 1;
return n * factorial(n - 1); // Multiplication after recursive call
}
// Tail recursive
function factorialTail(n, acc = 1) {
if (n <= 1) return acc;
return factorialTail(n - 1, n * acc); // Recursive call is the last operation
}
まとめ
| 概念 | 説明 |
|---|---|
| 再帰 | 関数が自分自身を呼び出すテクニック |
| 基底条件 | 再帰を停止する条件 |
| コールスタック | 再帰呼び出しが積まれるスタック |
| 分割統治法 | 分割→統治→結合の3ステップ |
| メモ化 | 計算結果をキャッシュして重複計算を回避 |
重要ポイント
- すべての再帰には基底条件と再帰条件が必要
- 分割統治法は問題を分割→統治→結合の3ステップで解く
- メモ化により指数時間の再帰を線形時間に改善できる
- 再帰が深すぎるとスタックオーバーフローが発生する
練習問題
問題1: 基本
再帰を使って、配列の中の最大値を見つける関数を実装してください。
問題2: 応用
再帰を使って、文字列が回文（前から読んでも後ろから読んでも同じ）かどうかを判定する関数を実装してください。
チャレンジ問題
再帰を使って、N個の要素から全ての組み合わせ（部分集合）を生成する関数を実装してください。
参考リンク
次回予告: Day 6では「ソートアルゴリズム」について学びます。主要なソートアルゴリズムの仕組みと性能を比較しましょう。