はじめに

フィボナッチ数列を計算する方法はいくつかありますが、その中でも再帰的アプローチとキャッシュ（メモ化）を使ったアプローチが一般的です。それぞれの方法には利点と欠点があります。本記事では、これらの方法について違いを明らかにします。

フィボナッチ数列とは？

フィボナッチ数列は、次のように定義される一連の数です。

F(0) = 0
F(1) = 1
F(n) = F(n-1) + F(n-2) for n >= 2
この数列は、0から始まり、次の数が前の2つの数の合計となります。

再帰的アプローチ

再帰的アプローチでは、フィボナッチ数列を再帰的に計算します。この方法はシンプルで理解しやすいですが、計算効率が悪い場合があります。

コード例

function fibonacci(n: number): number {
    if (n <= 1) {
        return n;
    }
    return fibonacci(n - 1) + fibonacci(n - 2);
}

メリット

シンプル: コードが簡潔で理解しやすい。
自然な表現: フィボナッチ数列の定義をそのままコードに反映している。

デメリット

計算効率が悪い: 同じ計算が何度も繰り返されるため、時間複雑度が指数関数的に増加します。具体的には、時間複雑度は O(2^n) となります。
スタックオーバーフローのリスク: 再帰の深さが大きくなると、スタックオーバーフローが発生するリスクがあります。

キャッシュを使ったアプローチ

キャッシュを使ったアプローチ（メモ化）は、計算済みの結果を保存し、重複する計算を避けることで効率を向上させます。

コード例

function fibonacci(n: number): number {
    let cache: number[] = new Array(n + 1).fill(0);

    function fib_memo(n: number): number {
        if (n <= 1) {
            return n;
        }
        if (cache[n] !== 0) {
            return cache[n];
        }
        cache[n] = fib_memo(n - 1) + fib_memo(n - 2);
        return cache[n];
    }

    return fib_memo(n);
}

メリット

計算効率が高い: 各計算結果をキャッシュに保存することで、重複する計算を避け、時間複雑度を O(n) に改善します。
再帰の利点を維持: 再帰的な構造を保ちながら、効率を大幅に向上させます。

デメリット

キャッシュの管理: キャッシュの初期化と管理が必要となり、コードが複雑になります。
メモリ使用量: キャッシュを保存するための追加メモリが必要です。

まとめ

再帰的アプローチとキャッシュを使ったアプローチの違いは、主に計算効率とメモリ使用量にあります。再帰的アプローチはシンプルで直感的ですが、計算効率が悪く、スタックオーバーフローのリスクがあります。一方、キャッシュを使ったアプローチは計算効率が高く、時間複雑度を大幅に改善できますが、キャッシュの管理とメモリ使用量が増加します。

フィボナッチ数列を計算する際には、計算量が少ない場合は再帰的アプローチを、計算量が多い場合はキャッシュを使ったアプローチを選択することが推奨されます。どちらの方法を選ぶかは、具体的な用途と制約条件に依存します。