Javaで学ぶ再帰アルゴリズム（前半）
Javaの再帰は、初心者にとって「少し難しそう」に見えるテーマですが、実は仕組みが分かればとてもシンプルです。 この前半では、再帰の基本構造、Javaでの書き方、そして代表的な例題を丁寧にかみ砕いて解説します。 後半では、ツリー構造や実務的な再帰、セキュリティ観点まで踏み込んでいきます。
再帰とは何か（Javaでの基本構造）
再帰とは「メソッドが自分自身を呼び出すこと」です。 Javaでは次のような形が基本になります。
void method() {
// ベースケース（終了条件）
if (/* 終わりの条件 */) {
return;
}
// 問題を少しだけ小さくして自分自身を呼び出す
method();
}
深掘り：再帰の2大原則
再帰は次の2つがそろって初めて成立します。
ベースケース（終了条件） どこで再帰を止めるかを必ず明確にする。 これがないと無限ループになり、Javaは StackOverflowError を投げます。
問題を小さくするステップ 毎回「少しだけ簡単な問題」にして自分自身を呼び出す。 これにより、必ずベースケースに近づいていきます。
この2つを理解することが、再帰の本質です。
Javaで最も基本的な再帰：カウントダウン
まずは、初心者向けに「カウントダウン」を再帰で書いてみます。
public static void countdown(int n) {
System.out.println(n);
if (n == 0) {
return; // ベースケース
}
countdown(n - 1); // 問題を小さくして再帰
}
public static void main(String[] args) {
countdown(5);
}
動きのイメージ
countdown(5) → 5 を表示して countdown(4) → 4 を表示して countdown(3) → … → countdown(0) で終了条件に到達し、再帰が止まる
再帰は「深く潜っていき、最後に戻りながら処理が終わる」という流れを持っています。
階乗（n!）を再帰で書く
再帰の代表例として必ず登場するのが「階乗」です。
public static int factorial(int n) {
if (n == 0) {
return 1; // ベースケース
}
return n * factorial(n - 1); // 再帰ステップ
}
public static void main(String[] args) {
System.out.println(factorial(5)); // 120
}
深掘り：数学の式と再帰の一致
階乗は数学的に次のように定義されます。
- 0! = 1
- n! = n × (n – 1)!
この「自分自身を使って定義する」形が、そのままJavaの再帰に対応しています。 再帰は数学的な定義をコードに落とし込むのに非常に向いています。
フィボナッチ数列（ただし注意付き）
フィボナッチ数列も再帰の代表例です。
public static int fib(int n) {
if (n == 0) return 0;
if (n == 1) return 1;
return fib(n - 1) + fib(n - 2);
}
深掘り：なぜ「注意付き」なのか
この再帰は美しいですが、計算量が爆発します。 同じ値を何度も計算するため、fib(40) などは非常に遅くなります。
後半では、この問題を解決する「メモ化」や「動的計画法」を扱います。
再帰の裏側：コールスタック
Javaはメソッドを呼び出すたびに「コールスタック」に情報を積み上げます。 再帰はこのスタックを深く使うため、終了条件がないとスタックが溢れます。
StackOverflowError
次のようなコードは危険です。
public static void bad(int n) {
bad(n + 1); // 終了条件がない
}
実行すると StackOverflowError が発生します。
深掘り：安全な再帰を書くためのポイント
- 必ず終了条件を書く
- 終了条件に確実に近づくようにする
- 深さが大きくなりすぎる可能性がある場合はループに切り替える
再帰とループの違い
再帰は「自分自身を呼び出す」 ループは「同じ処理を繰り返す」
どちらも繰り返し処理ですが、得意分野が違います。
再帰が向いている場面
- ツリー構造
- ネストが深いデータ
- 数学的な再帰定義
- 問題を自然に分割できる場合
ループが向いている場面
- 単純な繰り返し
- 深さが大きくなる可能性がある処理
- パフォーマンスが重要な場面
前半のまとめ
前半では、Javaの再帰の基礎と代表的な例を扱いました。
- 再帰は「自分自身を呼び出す」
- ベースケースと問題の縮小が必須
- 階乗やフィボナッチは再帰の典型例
- コールスタックの仕組みを理解すると再帰が分かりやすい
- 再帰とループは使い分けが重要
後半では、より実務的な再帰の使い方として
- ツリー構造の走査
- ファイル探索
- JSONやDOMの再帰処理
- セキュリティ観点での安全な再帰
- メモ化による高速化
などを深掘りしていきます。
