Javaで学ぶ再帰アルゴリズムの実例集（後半）
後半では、より実務的で「現場で本当に使う再帰」を中心に、初心者でも理解しやすいように丁寧にかみ砕いて解説していきます。 前半で学んだ ベースケース と 問題の縮小 を軸に、ツリー構造・ファイル探索・高速化・セキュリティまで踏み込んでいきます。
フォルダ階層やツリー構造を再帰でたどる
Javaでは、ツリー構造を扱う場面が非常に多くあります。 例えば、JSONのような入れ子データ、ファイル階層、組織図などです。 再帰は「深さが分からない構造」を自然に処理できるため、最適な手法になります。
ツリー構造の例
class Node {
String name;
List<Node> children;
Node(String name) {
this.name = name;
this.children = new ArrayList<>();
}
}
再帰でツリーを走査する
public static void traverse(Node node) {
System.out.println(node.name);
if (node.children == null || node.children.isEmpty()) {
return; // ベースケース
}
for (Node child : node.children) {
traverse(child); // 再帰ステップ
}
}
深掘り：なぜ再帰が最適なのか
ツリー構造は「どれだけ深く入れ子になっているか」が事前に分かりません。 ループだけで書こうとすると、深さに応じて複雑な処理が必要になります。 再帰なら「子があるなら子を処理する」という自然な形で書けるため、コードが圧倒的に読みやすくなります。
Javaでのファイル探索（実務で頻出）
Javaの現場では、フォルダ内のファイルを再帰的に探索する処理が頻繁に登場します。 ビルドツール、ログ解析、静的サイト生成、セキュリティスキャンなどで使われます。
再帰でファイルを探索する
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());
}
}
}
深掘り：実務での応用
この再帰は次のような場面で使われます。
- 静的サイトジェネレーター
- ビルドツール（Gradle, Maven）
- セキュリティスキャン
- ログ解析
- 自動テストのファイル探索
再帰は「構造をたどる」処理に非常に強いことが分かります。
JSONやネスト構造のデータを再帰で処理する
Javaでは JSON を扱う際に、入れ子になったデータを再帰で処理することがよくあります。
JSONの例（Jacksonを想定）
public static void printJson(JsonNode node) {
if (node.isValueNode()) {
System.out.println(node.asText());
return;
}
if (node.isObject()) {
node.fields().forEachRemaining(field -> {
System.out.println(field.getKey());
printJson(field.getValue());
});
}
if (node.isArray()) {
for (JsonNode child : node) {
printJson(child);
}
}
}
深掘り：再帰が「構造の違い」を吸収する
JSONは「値」「オブジェクト」「配列」が混在します。 再帰を使うと、構造の違いを自然に吸収しながら処理できます。
セキュリティ観点：危険な再帰と安全な再帰
再帰は便利ですが、セキュリティの観点では注意すべき点があります。
危険な再帰
ユーザー入力をそのまま再帰処理に使うと、意図的に「深すぎるデータ」を渡されて コールスタックを溢れさせる攻撃（DoS攻撃）が成立します。
public static void unsafe(Node node) {
unsafe(node); // 終了条件がない
}
安全な再帰
深さの上限を設けることで安全性を確保できます。
public static void safeTraverse(Node node, int depth, int maxDepth) {
if (depth > maxDepth) {
throw new RuntimeException("Depth limit exceeded");
}
if (node.children == null) return;
for (Node child : node.children) {
safeTraverse(child, depth + 1, maxDepth);
}
}
深掘り：セキュリティスペシャリストの視点
再帰は「入力の深さに比例して負荷が増える」ため、攻撃者にとって扱いやすい弱点になります。 そのため、実務では次のような対策が一般的です。
- 深さの上限を設ける
- 入力データを検証する
- 再帰ではなくループに置き換える
- 非同期処理で負荷を分散する
フィボナッチ数列の高速化（メモ化）
前半で扱ったフィボナッチは、再帰の美しい例ですが非効率でした。 ここでは「メモ化」を使って高速化します。
メモ化による高速化
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)); // 高速
}
深掘り：再帰と効率化の関係
再帰は「表現が美しい」反面、計算量が増えやすい構造です。 メモ化や動的計画法を組み合わせることで、 再帰の読みやすさと効率の両方を手に入れることができます。
再帰を使いこなすための最終ポイント
再帰は初心者にとって難しく感じることがありますが、 次の3つを意識すると一気に理解が進みます。
ベースケース
どこで終わるかを必ず明確にする。
問題を小さくする
毎回「少しだけ簡単な問題」にして自分自身を呼び出す。
コールスタックのイメージ
深く潜って、戻りながら計算する流れを頭の中で描く。
この3つを押さえれば、再帰は強力な武器になります。
