Elegant Access

今日のトピック (Today's Topic)

トピック: Recursion Basics
難易度: beginner
カテゴリー: Fundamentals

概念学習 (Concept Learning)

核心概念

**再帰（Recursion）**は、関数が自分自身を呼び出すことで、問題をより小さな類似したサブ問題に分解して解決するプログラミング技法です。再帰関数には2つの必須要素があります：

基底ケース（Base Case）：無限再帰を防ぐ停止条件
再帰ケース（Recursive Case）：関数が変更された入力で自分自身を呼び出す部分

再帰はマトリョーシカ人形のようなものです。各人形はより小さいバージョンの自分自身を含み、最小の人形（基底ケース）に到達するまで続きます。

重要ポイント

コールスタック：各再帰呼び出しはコールスタックに追加され、逆順（LIFO - Last In First Out）で解決される
メモリ使用量：再帰は各呼び出しにスタックメモリを使用するため、深い再帰はスタックオーバーフローを引き起こす可能性がある
2つの要件：すべての再帰関数は基底ケースを持ち、基底ケースに向かって進展する必要がある
再帰 vs 反復：ほとんどの再帰解法は反復解法に変換でき、その逆も可能
数学的性質：再帰は再帰的な数学的定義を持つ問題に特に適している

アルゴリズムステップ

基底ケースの特定：再帰なしで直接解決できる最も単純なケースを決定する
再帰ケースの定義：問題をより小さなサブ問題で表現する
進展の確保：各再帰呼び出しが基底ケースに近づくことを確認する
結果の結合：必要に応じて、再帰呼び出しの結果を結合して元の問題を解決する

実装 (Implementation)

説明

基本的な再帰パターン：

function recursiveFunction(input) {
    // 基底ケース - 再帰を停止する
    if (baseCondition) {
        return baseValue;
    }
    
    // 再帰ケース - 変更された入力で自分自身を呼び出す
    return recursiveFunction(modifiedInput);
}

例1：階乗

function factorial(n) {
    // 基底ケース
    if (n <= 1) return 1;
    
    // 再帰ケース: n! = n * (n-1)!
    return n * factorial(n - 1);
}

// factorial(5) = 5 * 4 * 3 * 2 * 1 = 120

例2：フィボナッチ数列

function fibonacci(n) {
    // 基底ケース
    if (n <= 1) return n;
    
    // 再帰ケース: fib(n) = fib(n-1) + fib(n-2)
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// fibonacci(6) = 8
// 数列: 0, 1, 1, 2, 3, 5, 8, 13...

例3：配列の合計

function sumArray(arr, index = 0) {
    // 基底ケース: 配列の末尾に到達
    if (index >= arr.length) return 0;
    
    // 再帰ケース: 現在の要素 + 残りの合計
    return arr[index] + sumArray(arr, index + 1);
}

// sumArray([1, 2, 3, 4, 5]) = 15

時間と空間計算量：

時間計算量：通常、単純な再帰では O(n)、ナイーブなフィボナッチのような分岐再帰では O(2^n)
空間計算量：O(n) - コールスタックの深さによる。各再帰呼び出しがスタックフレームを追加

エッジケースと一般的な誤り：

基底ケースを忘れる → 無限再帰とスタックオーバーフロー
到達できない基底ケース → 無限再帰
基底ケースに向かって進展しない → 無限再帰
再帰が深すぎる → スタックオーバーフローエラー
非効率的な再帰（ナイーブなフィボナッチなど）→ 指数時間計算量

練習問題 (Practice Problems)

問題リスト

LeetCode 509 - Fibonacci Number (Easy)
- 再帰を使用してn番目のフィボナッチ数を計算する
LeetCode 206 - Reverse Linked List (Easy)
- 単方向連結リストを再帰的に反転する
LeetCode 344 - Reverse String (Easy)
- 再帰を使用して文字列を反転する
LeetCode 70 - Climbing Stairs (Easy)
- 階段を登る方法の数を数える（メモ化付き再帰）
LeetCode 21 - Merge Two Sorted Lists (Easy)
- 2つのソート済み連結リストを再帰的にマージする

重要な詳細 (Important Details)

注意すべきエッジケース

空の入力：null、undefined、または空の配列の場合はどうなるか？
単一要素：基底ケースは n=1 または n=0 を正しく処理するか？
負の数：関数は負の入力を処理すべきか？
大きな入力：深い再帰はスタックオーバーフローを引き起こすか？

適用シナリオと制限

再帰を使用する場合：

木やグラフの走査
分割統治アルゴリズム（マージソート、クイックソート）
再帰的な数学的定義を持つ問題（階乗、フィボナッチ）
バックトラッキング問題（N-Queens、数独）
再帰的に自然に表現される問題

再帰を避ける場合：

非常に深い再帰（スタックオーバーフローのリスク）
メモ化なしのパフォーマンス重視のコード
反復解法がより単純で明確な場合
スタック空間が制限された組み込みシステム

拡張アプリケーションやバリエーション

末尾再帰：再帰呼び出しが最後の操作である最適化
相互再帰：2つ以上の関数が互いに再帰的に呼び出す
間接再帰：関数Aが関数Bを呼び出し、関数BがAを呼び出す
メモ化：冗長な計算を避けるために結果をキャッシュする
動的計画法：再帰のオーバーヘッドを避けるボトムアップアプローチ

今日の振り返り (Daily Reflection)

重要な収穫：再帰は、プログラミングしているとよく出てくるし、昔の面接でもよく聞かれていたトピックです。LeetCode の最初の簡単な問題でもほぼ必ず出てくるので、基本中の基本と言えます。

関連アルゴリズム：

分割統治（マージソート、クイックソート、二分探索）
木の走査（DFS、中順、前順、後順）
バックトラッキング（N-Queens、順列、組み合わせ）
動的計画法（再帰解法の最適化）
グラフ走査（DFS）

アルゴリズム日記

アルゴリズム日記 - Recursion Basics