再帰 ― メソッドが自分自身を呼び出す（軽く紹介）

導入

「大きな問題を、同じ形の小さな問題に分解して解く」という考え方があります。メソッドが自分自身を呼び出すことでこれを表現したものを 再帰 と呼びます。難しく感じたら、今は「こういう書き方がある」と知っておくだけでも十分です。

説明

階乗（5! = 5 × 4 × 3 × 2 × 1）を再帰で計算してみましょう。

public class Main {
    public static void main(String[] args) {
        System.out.println(factorial(5));
    }

    static int factorial(int n) {
        if (n <= 1) {
            return 1;          // ベースケース：ここで再帰が止まる
        }
        return n * factorial(n - 1);  // n × (n-1の階乗)
    }
}

• factorial(n - 1) … メソッドの中で自分自身（factorial）を呼び出しています。これが再帰です。
• if (n <= 1) { return 1; } … ベースケース（終了条件） です。これがないと、メソッドが自分自身を呼び続けて無限に終わらなくなってしまいます（スタックオーバーフローというエラーになります）。
• factorial(5) は 5 * factorial(4)、factorial(4) は 4 * factorial(3)…と、factorial(1) にたどり着くまで小さくなっていき、そこから答えが順に掛け合わされて戻ってきます。

再帰は「同じ処理を、少しずつ小さくしながら繰り返す」for・while の親戚のようなものだと考えると理解しやすくなります。

やってみよう

下のエディタで factorial に渡す数を変えて、結果がどう変わるか確かめましょう。if (n <= 1) を消してみて、何が起こるか（実行が終わらない・エラーになる）も観察してみてください。

演習

再帰でフィボナッチ数列の n 番目を求める fibonacci(int n) を作ってください（fibonacci(0) = 0、fibonacci(1) = 1、それ以降は直前2つの和）。fibonacci(7) を表示してください（結果は 13）。