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では「ソートアルゴリズム」について学びます。主要なソートアルゴリズムの仕組みと性能を比較しましょう。