Java | 再帰の高速化テクニック

Java

2026.07.17

Javaで学ぶ「再帰の高速化テクニック」（前半）
再帰が遅くなる理由を理解する
1. 再帰が遅くなる根本原因
フィボナッチ数列で見る「非効率な再帰」
1. 深掘り：なぜこのコードは遅いのか
メモ化（Memoization）による高速化
1. メモ化を使ったフィボナッチ
2. 深掘り：メモ化が高速化する理由
メモ化の本質を理解する
1. メモ化の本質
メモ化が向いている場面
メモ化の注意点
1. メモ化の弱点
前半のまとめ

Javaで学ぶ「再帰の高速化テクニック」（前半）

再帰は美しく書ける反面、処理が遅くなりやすいという弱点があります。特に Java の再帰は「関数呼び出しのコスト」や「スタックの深さ」に影響されるため、高速化テクニックを理解することは初心者にとって大きなステップになります。

前半では、再帰が遅くなる理由を丁寧にかみ砕きながら、最も基本的で効果の高い高速化テクニックである メモ化（Memoization） を中心に解説します。後半では、より高度な 動的計画法（DP） や 末尾再帰最適化、そして実務でのパフォーマンス判断まで踏み込みます。

再帰が遅くなる理由を理解する

再帰の高速化を学ぶ前に、「なぜ遅くなるのか」を理解することが重要です。理由を知らないまま高速化テクニックを使うと、応用が効かなくなるからです。

再帰が遅くなる根本原因

再帰が遅くなる典型的な理由は次の2つです。

同じ計算を何度も繰り返す フィボナッチ数列のように、 fib(n) を計算するために fib(n-1) と fib(n-2) を呼び出し、その中でまた同じ値を何度も計算してしまう。

関数呼び出しのコストが積み重なる Javaではメソッド呼び出しのたびにスタックフレームが積まれるため、深い再帰はオーバーヘッドが大きくなる。

この2つが組み合わさると、「見た目はシンプルなのに、実行するととても遅い」という状況が生まれます。

フィボナッチ数列で見る「非効率な再帰」

まずは、典型的な「遅い再帰」の例を見てみましょう。

public static int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    return fib(n - 1) + fib(n - 2);
}

public static int fib(int n) {
    if (n == 0) return 0;
    if (n == 1) return 1;

    return fib(n - 1) + fib(n - 2);
}

Java

深掘り：なぜこのコードは遅いのか

fib(5) を例にすると、内部では次のような呼び出しが発生します。

fib(5)
- fib(4)
  - fib(3)
    - fib(2)
      - fib(1)
      - fib(0)
    - fib(1)
  - fib(2)
    - fib(1)
    - fib(0)
- fib(3)
  - fib(2)
    - fib(1)
    - fib(0)
  - fib(1)

ここで注目すべきは fib(2) や fib(3) が何度も計算されていることです。これが指数的な計算量（O(2ⁿ））を生み、 fib(40) などは非常に遅くなります。

メモ化（Memoization）による高速化

メモ化とは「一度計算した結果を保存しておき、次回は再計算しない」テクニックです。再帰の高速化では最も基本であり、最も効果が高い方法です。

メモ化を使ったフィボナッチ

import java.util.HashMap;
import java.util.Map;

public static int fibMemo(int n, Map<Integer, Integer> memo) {
    if (memo.containsKey(n)) {
        return memo.get(n); // 過去の結果を再利用
    }

    if (n == 0) return 0;
    if (n == 1) return 1;

    int result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    memo.put(n, result); // 計算結果を保存
    return result;
}

public static void main(String[] args) {
    Map<Integer, Integer> memo = new HashMap<>();
    System.out.println(fibMemo(40, memo)); // 高速に計算できる
}

import java.util.HashMap;
import java.util.Map;

public static int fibMemo(int n, Map<Integer, Integer> memo) {
    if (memo.containsKey(n)) {
        return memo.get(n); // 過去の結果を再利用
    }

    if (n == 0) return 0;
    if (n == 1) return 1;

    int result = fibMemo(n - 1, memo) + fibMemo(n - 2, memo);
    memo.put(n, result); // 計算結果を保存
    return result;
}

public static void main(String[] args) {
    Map<Integer, Integer> memo = new HashMap<>();
    System.out.println(fibMemo(40, memo)); // 高速に計算できる
}