Java再帰処理の理解：仕組み、例、トレードオフ

Java再帰処理

このガイドでは、Javaの再帰メソッドを解説し、古典的な階乗の例を通じて歩み、再帰の利点と欠点を評価します。

Javaにおいて、自分自身を呼び出すメソッドを再帰メソッドと呼び、この全体的な技法を再帰と呼びます。シンプルな現実世界の例は、互いに向き合った2つの鏡です：各反射がさらに別の鏡像となり、光が吸収されるまで繰り返されます。

再帰の仕組み

上図では、recurse()メソッドがmain()から呼び出されています（通常の呼び出し）。recurse()内部で、同じメソッドが再び自分自身を呼び出し、再帰呼び出しを作ります。無限ループを防ぐため、各再帰呼び出しには終了条件が必要で、通常はif…else文で実装されます。

例：再帰を使った数値の階乗

class Factorial { static int factorial(int n) { if (n != 0) // 終了条件 return n * factorial(n - 1); // 再帰呼び出し else return 1; } public static void main(String[] args) { int number = 4, result; result = factorial(number); System.out.println(number + " factorial = " + result); } }

出力：

4 factorial = 24

factorial()メソッドはmain()から引数numberで呼び出されます。factorial()内部で、以下の行：

return n * factorial(n-1);

により、メソッドがデクリメントされた値で自分自身を呼び出します。n = 4から始まり、呼び出しは4 → 3 → 2 → 1 → 0と進行します。nが0になると、if条件が失敗し、1を返します。累積された積がコールスタックを通じてmain()まで伝播します。

階乗プログラムの実行過程

下図は実行時のコールスタックの変化を示しています。

再帰の利点と欠点

利点：再帰的なパターンに自然に適合する問題（木の走査、組み合わせ生成など）でコードがシンプルになります。多くの場合、より短く読みやすい実装になります。
欠点：各再帰呼び出しはスタック領域を消費し、深い再帰ではスタックオーバーフローを引き起こす可能性があります。再帰的解法は一般に反復的解法よりメモリ効率が悪く、実行速度も遅くなりがちです。

全体として、再帰は高いメモリ使用量と潜在的なパフォーマンスオーバーヘッドと引き換えにエレガントな解法を提供します。深さが限られる多くのユースケースでは、このトレードオフは価値があります。

推奨読書：再帰の利点と欠点とは？

Javaのfinalキーワード完全解説：変数、メソッド、クラスでの活用法 Java instanceof演算子完全ガイド：基本から継承・インターフェースまで

Java