Java | フィボナッチを高速化する方法

Java

2026.07.17

Javaで学ぶ「フィボナッチを高速化する方法」（前半）
フィボナッチ数列の定義をコードで確認する
なぜ素直な再帰フィボナッチは遅いのか
まずはループ版に書き換えてみる（O(n) への改善）
深掘り：ループ版の動きを具体的に追ってみる
メモ化（Memoization）という考え方を知る
Javaで書くメモ化付きフィボナッチ（再帰＋配列）
深掘り：メモ化の効果を具体例で感じる
再帰版・ループ版・メモ化版の違いを直感で整理する

Javaで学ぶ「フィボナッチを高速化する方法」（前半）

フィボナッチ数列は、アルゴリズム学習の定番テーマです。しかし、素直な再帰で書いたフィボナッチは「とんでもなく遅い」コードになります。前半では、まず「なぜ遅いのか」を丁寧にほどき、そのうえでループ版・メモ化版という、初心者でもすぐに使える高速化の入り口を解説していきます。後半では、さらに一歩進んだ高速化（動的計画法・行列累乗など）に踏み込みます。

フィボナッチ数列の定義をコードで確認する

フィボナッチ数列は次のように定義されます。

$F (0) = 0$ $F (1) = 1$ $F (n) = F (n - 1) + F (n - 2)$ （n ≥ 2）

Javaで最も教科書的な書き方をすると、こうなります。

public static int fibRecursive(int n) {
    if (n <= 1) {
        return n;
    }
    return fibRecursive(n - 1) + fibRecursive(n - 2);
}

public static int fibRecursive(int n) {
    if (n <= 1) {
        return n;
    }
    return fibRecursive(n - 1) + fibRecursive(n - 2);
}

Java

見た目はとても美しいですが、このコードには大きな問題があります。それが「計算量が爆発する」という点です。

なぜ素直な再帰フィボナッチは遅いのか

fibRecursive(40) や fibRecursive(45) を呼んでみると、「いつまで経っても終わらない」感覚を味わうことになります。

理由は、同じ値を何度も何度も計算しているからです。

例えば fibRecursive(5) を考えてみましょう。

fib(5) は fib(4) と fib(3) を呼びます。 fib(4) は fib(3) と fib(2) を呼びます。 fib(3) は fib(2) と fib(1) を呼びます。

ここで注目すべきなのは、fib(3) や fib(2) が何度も登場していることです。同じ値を何度も再計算しているため、呼び出し回数が指数関数的に増えていきます。

この「同じ計算の繰り返し」が、素直な再帰フィボナッチを「遅いコード」にしている本質です。

まずはループ版に書き換えてみる（O(n) への改善）

最初の高速化として、再帰をやめてループで書く方法があります。これは「下から順番に計算していく」発想です。

public static int fibLoop(int n) {
    if (n <= 1) return n;

    int a = 0; // F(0)
    int b = 1; // F(1)

    for (int i = 2; i <= n; i++) {
        int c = a + b; // F(i) = F(i-1) + F(i-2)
        a = b;
        b = c;
    }
    return b;
}

public static int fibLoop(int n) {
    if (n <= 1) return n;

    int a = 0; // F(0)
    int b = 1; // F(1)

    for (int i = 2; i <= n; i++) {
        int c = a + b; // F(i) = F(i-1) + F(i-2)
        a = b;
        b = c;
    }
    return b;
}

Java

このコードは、次のような流れで動きます。

最初に F(0) = 0, F(1) = 1 を用意する F(2), F(3), …, F(n) を順番に計算していく常に「直前2つの値」だけを持ち歩く

重要なのは、「同じ値を二度と計算しない」という点です。これにより、計算量は O(n) に改善されます。

深掘り：ループ版の動きを具体的に追ってみる

例えば fibLoop(5) を呼び出したときの動きを追ってみます。

最初に a = 0（F(0）） b = 1（F(1））

i = 2 のとき c = a + b = 0 + 1 = 1（F(2）） a = b = 1 b = c = 1

i = 3 のとき c = a + b = 1 + 1 = 2（F(3）） a = b = 1 b = c = 2

i = 4 のとき c = a + b = 1 + 2 = 3（F(4）） a = b = 2 b = c = 3

i = 5 のとき c = a + b = 2 + 3 = 5（F(5）） a = b = 3 b = c = 5

最後に b を返すので、結果は 5 になります。このように、ループ版は「一度通るだけ」で目的の値に到達します。

メモ化（Memoization）という考え方を知る

ループ版は十分速いですが、「再帰の形を保ったまま高速化したい」という場面もあります。

そこで登場するのが メモ化（Memoization） です。メモ化とは、「一度計算した結果を覚えておいて、次回は再利用する」というテクニックです。

フィボナッチにメモ化を適用すると、「同じ値を何度も計算する」という問題を解消できます。

Javaで書くメモ化付きフィボナッチ（再帰＋配列）

メモ化付きフィボナッチの基本形は次のようになります。

public static int fibMemo(int n, int[] memo) {
    if (n <= 1) return n;

    if (memo[n] != -1) {
        return memo[n];
    }

    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

public static int fibMemoMain(int n) {
    int[] memo = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        memo[i] = -1;
    }
    return fibMemo(n, memo);
}

public static int fibMemo(int n, int[] memo) {
    if (n <= 1) return n;

    if (memo[n] != -1) {
        return memo[n];
    }

    memo[n] = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    return memo[n];
}

public static int fibMemoMain(int n) {
    int[] memo = new int[n + 1];
    for (int i = 0; i <= n; i++) {
        memo[i] = -1;
    }
    return fibMemo(n, memo);
}