Java の再帰

再帰（Recursion）とは、メソッドが自分自身を呼び出す手法のことです。このテクニックを使用すると、複雑な問題を、より解決しやすい単純な問題へと分解することができます。

再帰は最初は少し理解しにくいかもしれませんが、実際にコードを動かして「何が起きているか」を観察するのが、習得への一番の近道です。

1. 再帰の具体例：1から10までの合計

2つの数値を足すのは簡単ですが、ある範囲の数値をすべて足す処理は少し複雑です。以下の例では、再帰を使用して「数値の範囲を足す」という問題を、「2つの数値を足す」という単純なタスクの繰り返しに分解しています。

1.1 数値合計のコード例

public class Main {
  public static int sum(int k) {
    if (k > 0) {
      // 自分自身を呼び出し、kを1ずつ減らしていく
      return k + sum(k - 1);
    } else {
      // kが0になったら終了
      return 0;
    }
  }

  public static void main(String[] args) {
    int result = sum(10);
    System.out.println(result);
  }
}

1.2 処理のステップ解説

sum() メソッドが呼び出されると、プログラムは内部で以下のようなステップを辿ります：

10 + sum(9)
10 + ( 9 + sum(8) )
10 + ( 9 + ( 8 + sum(7) ) )
...
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + sum(0)
10 + 9 + 8 + 7 + 6 + 5 + 4 + 3 + 2 + 1 + 0

k が 0 になったとき、メソッドは自分自身を呼び出すのをやめ、最終的な結果を返します。

2. 停止条件 (Halting Condition)

ループが「無限ループ」に陥る可能性があるのと同様に、再帰メソッドも「無限再帰」に陥るリスクがあります。無限再帰とは、メソッドが自分自身を呼び出すのをやめられなくなる状態です。

すべての再帰メソッドには、必ず停止条件（Halting Condition）が必要です。これは、メソッドが呼び出しを停止するための条件（ベースケース）です。

2.1 範囲指定の合計と停止条件

次の例では、start から end までの範囲の合計を計算します。ここでの停止条件は end が start 以下になったときです。

public class Main {
  public static int sum(int start, int end) {
    if (end > start) {
      return end + sum(start, end - 1);
    } else {
      return end; // endがstartに到達したら終了
    }
  }

  public static void main(String[] args) {
    int result = sum(5, 10); // 5+6+7+8+9+10
    System.out.println(result);
  }
}

3. 定番の再帰：階乗（Factorial）の計算

数学的な計算、特に階乗 n! は再帰の代表的な例です。5!（5の階乗）は 5 x 4 x 3 x 2 x 1 = 120 となります。

3.1 階乗計算のコード例

n! = n x (n - 1)

public class Main {
  static int factorial(int n) {
    if (n > 1) {
      return n * factorial(n - 1);
    } else {
      return 1; // 1以下になったら終了
    }
  }

  public static void main(String[] args) {
    System.out.println("5の階乗は " + factorial(5));
  }
}