フィボナッチ数列（再帰）

再帰アルゴリズムの基本概念と指数的計算量の問題を学ぼう

O(2^n)

時間計算量（指数的）

O(n)

空間計算量

中級

難易度

再帰

手法

🔧 実行設定

計算対象:

F(5)

予想呼び出し回数:

約 9 回

n の値（0以上25以下）

📚 推奨値

🔢 フィボナッチ数列

F(0)=0, F(1)=1, F(2)=1, F(3)=2, F(4)=3, F(5)=5, F(6)=8, F(7)=13

🔄

アルゴリズムを実行してください

左側の設定パネルからnの値を設定し、「フィボナッチ計算実行」ボタンを押してください

💻 実装例（JavaScript）

function fibonacci(n) {
    // ベースケース：停止条件
    if (n <= 1) {
        return n;
    }
    
    // 再帰ケース：自分自身を呼び出し
    return fibonacci(n - 1) + fibonacci(n - 2);
}

// 使用例
console.log(fibonacci(0));  // 0
console.log(fibonacci(1));  // 1
console.log(fibonacci(5));  // 5
console.log(fibonacci(10)); // 55

// 数列を生成
function generateFibonacciSequence(count) {
    const sequence = [];
    for (let i = 0; i < count; i++) {
        sequence.push(fibonacci(i));
    }
    return sequence;
}

console.log(generateFibonacciSequence(10));
// [0, 1, 1, 2, 3, 5, 8, 13, 21, 34]

// 注意：この実装は O(2^n) の時間計算量で非効率
// 実用的な用途には最適化が必要

⚡ 最適化の必要性

問題点

• 同じ計算を何度も繰り返す
• 計算量が指数的に増加 O(2^n)
• n=40で約10億回の関数呼び出し
• 実用的でない実行時間

解決策

• メモ化（計算済み結果をキャッシュ）
• 動的プログラミング（ボトムアップ）
• 反復的実装（ループ使用）
• 行列累乗による O(log n) 解法