Java | 再帰とループの最適な使い分け

Javaで学ぶ「再帰とループの最適な使い分け」（後半）

前半では、再帰とループの性格・得意分野・安全性について、ざっくりと軸を作りました。 後半では、その軸を「実務でどう判断するか」「どう書き換えるか」というレベルまで落とし込みます。 読者が自分でコードを書くときに、「これは再帰で書くべきか？ループにすべきか？」を判断できるようになることがゴールです。

実務での判断パターンを具体的にする

再帰とループの使い分けは、感覚ではなく「パターン」で覚えると強くなります。 ここでは、現場でよく出てくる典型パターンを、初心者向けにかみ砕いて整理していきます。

パターン1：ツリー構造・階層構造は基本的に再帰

フォルダ階層、組織図、JSON、DOMツリーなど、「入れ子」になっているものは、再帰が自然に書けます。

例として、フォルダ内のファイルをすべて表示する処理を考えます。

import java.io.File;

public static void walk(File dir) {
    File[] files = dir.listFiles();
    if (files == null) return;

    for (File file : files) {
        if (file.isDirectory()) {
            walk(file); // 再帰
        } else {
            System.out.println(file.getAbsolutePath());
        }
    }
}

import java.io.File;

public static void walk(File dir) {
    File[] files = dir.listFiles();
    if (files == null) return;

    for (File file : files) {
        if (file.isDirectory()) {
            walk(file); // 再帰
        } else {
            System.out.println(file.getAbsolutePath());
        }
    }
}

このコードは、「ディレクトリなら中身をもう一度調べる」「ファイルなら表示する」という人間の感覚に近い形で書かれています。 ループだけで同じことをしようとすると、深さごとに処理を分ける必要があり、コードが一気に読みにくくなります。

ここで深掘りしたいポイントは、「構造そのものが再帰的なら、コードも再帰的に書くと読みやすい」ということです。 ツリー構造はまさにその典型で、再帰が最も輝く場面です。

パターン2：配列・リスト・範囲の処理は基本的にループ

一方で、「配列の全要素を処理する」「1からnまで繰り返す」といった線形な処理は、ループが向いています。

例えば、配列の最大値を求める処理を考えます。

ループで書くとこうなります。

public static int maxLoop(int[] arr) {
    int max = Integer.MIN_VALUE;
    for (int value : arr) {
        if (value > max) {
            max = value;
        }
    }
    return max;
}

public static int maxLoop(int[] arr) {
    int max = Integer.MIN_VALUE;
    for (int value : arr) {
        if (value > max) {
            max = value;
        }
    }
    return max;
}

これを再帰で書くこともできますが、初心者にとっては読みづらくなりがちです。

public static int maxRecursive(int[] arr, int index) {
    if (index == arr.length - 1) {
        return arr[index]; // ベースケース
    }
    int nextMax = maxRecursive(arr, index + 1);
    return Math.max(arr[index], nextMax);
}

public static int maxRecursive(int[] arr, int index) {
    if (index == arr.length - 1) {
        return arr[index]; // ベースケース
    }
    int nextMax = maxRecursive(arr, index + 1);
    return Math.max(arr[index], nextMax);
}

どちらも正しいですが、「配列の先頭から末尾まで順番に見る」という線形なイメージに対しては、ループの方が直感的です。 実務でも、こうした線形処理はほぼループで書かれます。

再帰からループへの書き換えを体験する

使い分けを本当に身につけるには、「再帰で書いたものをループに書き換える」練習が効果的です。 ここでは、前半で扱った「1からnまでの合計」を題材に、書き換えの流れをもう一度丁寧に追ってみます。

再帰版の合計

public static int sumRecursive(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sumRecursive(n - 1);
}

public static int sumRecursive(int n) {
    if (n == 0) {
        return 0;
    }
    return n + sumRecursive(n - 1);
}

このコードの頭の中でのイメージは、「n を足して、残りは自分に任せる」です。 sumRecursive(5) は内部で sumRecursive(4) を呼び出し、さらに sumRecursive(3)…と続きます。

ループ版への書き換え

これをループにすると、次のようになります。

public static int sumLoop(int n) {
    int result = 0;
    for (int i = 1; i <= n; i++) {
        result += i;
    }
    return result;
}

public static int sumLoop(int n) {
    int result = 0;
    for (int i = 1; i <= n; i++) {
        result += i;
    }
    return result;
}

ここで重要なのは、「再帰で減らしていた n を、ループでは i という変数で増やしている」という対応関係です。 再帰では「n を小さくしてベースケースに近づける」 ループでは「i を動かして範囲を走査する」

この対応を意識すると、「再帰で書いたけれど、これはループにした方がいいな」という判断がしやすくなります。

セキュリティ・安定性の観点からの使い分け

セキュリティスペシャリストの視点で見ると、再帰とループの使い分けにはもう一つ重要な軸があります。 それは「入力によって深さが変わるかどうか」です。

入力次第で深さが暴走する再帰は危険

例えば、ユーザーがアップロードした JSON を再帰で処理する場合、 攻撃者が「異常に深い入れ子構造」を送ってくる可能性があります。

public static void process(JsonNode node) {
    // ベースケースがあっても、深さが極端に深いと StackOverflowError の可能性
    if (node.isValueNode()) return;
    for (JsonNode child : node) {
        process(child);
    }
}

public static void process(JsonNode node) {
    // ベースケースがあっても、深さが極端に深いと StackOverflowError の可能性
    if (node.isValueNode()) return;
    for (JsonNode child : node) {
        process(child);
    }
}

このようなコードは、入力次第で再帰の深さが制御されてしまうため、 DoS攻撃（サービス妨害）の入り口になり得ます。

深さに上限を設ける、またはループに切り替える

安全にするためには、次のような工夫が必要です。

public static void processSafe(JsonNode node, int depth, int maxDepth) {
    if (depth > maxDepth) {
        throw new RuntimeException("Depth limit exceeded");
    }

    if (node.isValueNode()) return;
    for (JsonNode child : node) {
        processSafe(child, depth + 1, maxDepth);
    }
}

public static void processSafe(JsonNode node, int depth, int maxDepth) {
    if (depth > maxDepth) {
        throw new RuntimeException("Depth limit exceeded");
    }

    if (node.isValueNode()) return;
    for (JsonNode child : node) {
        processSafe(child, depth + 1, maxDepth);
    }
}

あるいは、可能であれば再帰ではなくループやキューを使って「幅優先」や「深さ制限付き」の探索に切り替えます。

セキュリティの観点から言えば、「入力によって深さが決まる再帰」は常に警戒対象です。 そのような場面では、深さ制限・入力検証・ループへの置き換えをセットで考えるべきです。

パフォーマンスの観点からの使い分け

パフォーマンスの観点では、「計算量」と「オーバーヘッド」の両方を意識する必要があります。

再帰は、重複計算が多いと一気に遅くなります。 フィボナッチ数列の素朴な再帰が典型例です。

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);
}

このような再帰は、メモ化や動的計画法で高速化するか、 そもそもループで書き直すべきです。

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

    int prev = 0;
    int curr = 1;
    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

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

    int prev = 0;
    int curr = 1;
    for (int i = 2; i <= n; i++) {
        int next = prev + curr;
        prev = curr;
        curr = next;
    }
    return curr;
}

ここで深掘りしたいのは、「再帰の美しさ」と「ループの効率」のバランスです。 アルゴリズムの説明や学習では再帰が分かりやすいことも多いですが、 実務で大量データを処理するなら、最終的にはループや DP に落とし込むことが多いです。

練習問題レベルの「どっちで書くべきか」ケース集

最後に、読者が自分で判断するための「感覚のチェックポイント」をいくつか挙げておきます。

配列の合計、最大値、最小値、ソート前の単純な走査 こうした線形処理は、基本的にループで書くのが定石です。

フォルダ階層の探索、ツリー構造の走査、JSONやDOMの入れ子処理 こうした入れ子構造は、再帰で書くと自然で読みやすくなります。

フィボナッチ、階乗、組み合わせ数などの数学的な定義 学習段階では再帰で書いて理解し、 実務ではループや DP に落とし込む、という二段構えが現実的です。

入力によって深さが変わる処理 セキュリティと安定性の観点から、深さ制限やループへの置き換えを検討すべき領域です。

後半のまとめと次のステップ

後半では、再帰とループの使い分けを「実務でどう判断するか」というレベルまで具体化しました。

構造が入れ子なら再帰、線形ならループ。 安全性とパフォーマンスが重要なら、深さや計算量を意識して選ぶ。 学習では再帰でアルゴリズムの本質を理解し、 実務ではループや動的計画法に落とし込む。

この感覚が身につくと、「再帰とループ、どっちを使うべきか？」という問いに対して、 自分なりの答えを持てるようになります。

もしさらに踏み込みたい読者向けには、 ツリー探索アルゴリズム（DFS・BFS）、動的計画法、 そしてセキュリティを意識した入力検証などが、次の良いステップになります。