後半：Javaで「使える」再帰アルゴリズムを身につける
前半で、再帰の基本的な感覚と Java における動きはつかめてきたと思う。
後半では、もう少しアルゴリズム寄りに踏み込んで、「典型パターン」と「考え方の型」をしっかり体に入れていこう。
階乗 factorial で再帰の型を固める
階乗の定義と再帰のつながり
階乗（factorial）は、次のように定義される。
(0! = 1)
(n! = n \times (n-1)!) （(n > 0) のとき）
この「自分自身を使って自分を定義している」形が、そのまま再帰メソッドの形になる。
再帰が一番きれいにハマる典型例だ。
Java での階乗の再帰実装
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)! と書く部分が再帰ステップになっている。
この「数学の再帰的な定義を、そのままコードに写す」という感覚は、アルゴリズムを読む・書くうえでかなり強い武器になる。
フィボナッチ数列と「やりすぎ再帰」の罠
フィボナッチ数列の再帰定義
フィボナッチ数列は、次のように定義される。
fib(0) = 0
fib(1) = 1
fib(n) = fib(n-1) + fib(n-2) （n ≥ 2）
これも、定義そのものが再帰になっているパターンだ。
Java での素直な再帰実装
public static int fib(int n) {
if (n == 0) { // ベースケース1
return 0;
}
if (n == 1) { // ベースケース2
return 1;
}
return fib(n - 1) + fib(n - 2); // 再帰ステップ
}
public static void main(String[] args) {
System.out.println(fib(6)); // 8
}
見た目はとても美しい。
定義とコードがほぼ同じで、「アルゴリズムをそのまま書いた」感じになっている。
パフォーマンスを深掘りする
ここが重要ポイントだ。
この実装は、n が大きくなると一気に遅くなる。
理由は、「同じ値を何度も何度も計算している」から。
fib(6) を例にすると、fib(5) と fib(4) を呼び、fib(5) は fib(4) と fib(3) を呼び…という具合に、fib(4) や fib(3) が何度も再計算される。
アルゴリズムの言葉で言えば、時間計算量が指数関数的に増える。
セキュリティ・運用の視点から見ると、「少し大きな入力を与えただけで CPU を食い尽くす」ようなコードは、サービス妨害（DoS）的な弱点になり得る。
ここで押さえておきたいのは、「再帰で書ける＝良いアルゴリズム」ではないということ。
再帰は表現方法であって、「速さ」「メモリ」「安全性」は別に評価しなければならない。
配列と文字列を再帰で扱う
配列の合計を再帰で求める
Java では配列を扱うことが多いので、配列を題材にした再帰を見ておこう。
public static int sumArray(int[] arr, int index) {
if (index == arr.length) { // ベースケース：末尾まで来たら 0
return 0;
}
return arr[index] + sumArray(arr, index + 1); // 今の要素 + 残りの合計
}
public static void main(String[] args) {
int[] nums = {1, 2, 3, 4};
System.out.println(sumArray(nums, 0)); // 10
}
ここでやっていることは、とてもシンプルだ。
配列の末尾まで来たら合計は 0 とみなす。
そうでなければ、「今の要素」＋「残りの要素の合計」として問題を一歩だけ小さくしている。
この「今の1つ＋残りを再帰に任せる」というパターンは、配列・文字列・リストなどでよく使う再帰の基本形になる。
文字列を逆順にする再帰
次は文字列を逆順にする例を見てみよう。
例えば “abcd” を “dcba” にしたい、という問題だ。
public static String reverse(String s) {
if (s.isEmpty()) { // ベースケース：空文字列
return "";
}
return reverse(s.substring(1)) + s.charAt(0);
}
public static void main(String[] args) {
System.out.println(reverse("abcd")); // dcba
}
考え方はこうだ。
文字列 s を逆順にしたいとき、「先頭以外を逆順にしたもの」の末尾に「先頭の1文字」をくっつければよい。
つまり、「残りを再帰に任せて、最後に自分の分を足す」という構造になっている。
ここでも、「先頭」と「残り」に分けるという分解の仕方が出てきている。
配列でも文字列でも、「先頭＋残り」という分解は再帰の鉄板パターンだ。
木構造・階層構造と再帰：Java らしい本番の出番
シンプルな木構造クラスを定義する
Java では、ツリー状のデータ構造を扱うことが多い。
例えば、次のようなノードクラスを考えてみる。
import java.util.List;
class Node {
String name;
List<Node> children;
Node(String name, List<Node> children) {
this.name = name;
this.children = children;
}
}
この木構造の全てのノードの name を表示したいとする。
再帰で木構造をたどる
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 で業務システムやツールを書くときにも、こうした木構造を再帰で処理する場面はかなり多い。
再帰とループ、どちらを選ぶべきか
思考としての再帰、実装としてのループ
実務寄りの話をすると、「頭の中では再帰で考えて、コードとしてはループで書く」ことがよくある。
理由は、ループの方が
スタックオーバーフローの心配がない
パフォーマンスが安定しやすい
JVM の最適化が効きやすい
といったメリットを持っているからだ。
ただし、木構造や再帰的な定義をそのまま表現したいときは、再帰の方が圧倒的に読みやすいことも多い。
「読みやすさ」と「安全性・速さ」のバランスをどう取るかが、プロの判断ポイントになる。
セキュリティ・パフォーマンスの視点
入力サイズがどこまで大きくなり得るか。
最悪ケースで再帰の深さはどれくらいか。
同じ計算を何度も繰り返していないか。
このあたりをざっくりでもいいので意識しておくと、「とりあえず動くコード」から一段レベルアップできる。
特に、ユーザー入力や外部データをそのまま再帰の深さに反映させるようなコードは、慎重に設計した方がいい。
再帰を書くときの「思考の型」
先にベースケースを決める
再帰を書くときは、まず「どんな状態になったら、もう再帰をやめていいか」を決める。
ここを先に決めることで、「必ず終わる」ことが保証される。
n が 0 になったら終わり。
配列の末尾まで来たら終わり。
子どもがいないノードまで来たら終わり。
この「終点」を先に決める癖は、バグ防止にもセキュリティにも効く。
問題を「一歩だけ」小さくする
次に、「今の問題を一歩だけ小さくする」ことを考える。
n! を「n × (n-1)!」にする。
配列全体の合計を「今の要素＋残りの合計」にする。
木全体の処理を「今のノード＋子ノードの処理」にする。
ここで大事なのは、「自分で全部やろうとしない」こと。
自分は一歩だけ進めて、残りは再帰呼び出しに任せる、というマインドセットが再帰のコアだ。
スタックの深さと計算量をざっくり見積もる
最後に、「この再帰はどれくらい深くなるか」「呼び出し回数はどれくらいか」をざっくりでいいのでイメージする。
深さが n で、呼び出し回数もだいたい n なら、まだわかりやすい。
フィボナッチのように、呼び出し回数が指数関数的に増えるものは要注意だ。
この「最悪ケースをざっくり想像する」癖は、アルゴリズム設計とセキュリティ設計の両方で効いてくる。
まとめ：再帰は「問題分解の筋トレ」
ここまでで、Java におけるアルゴリズムと再帰関数を、かなり実戦寄りに見てきた。
再帰は「自分自身を呼ぶメソッド」だけれど、本質は「大きな問題を同じ形の小さな問題に分解する技術」だということ。
ベースケースと再帰ステップを先に設計することで、「必ず終わる」「読みやすい」再帰になること。
階乗・フィボナッチ・配列・文字列・木構造など、典型パターンを通して再帰の型を体に入れられること。
再帰は美しいが、スタックの深さや計算量、データコピーのコストには常に注意が必要なこと。
