初心者向け：Javaで学ぶ再帰アルゴリズムの基本と応用

プログラミングを学ぶ中で「再帰」という言葉を耳にすることがあるでしょう。再帰処理は、問題を小さく分割して解決する強力な手法であり、Javaでのアルゴリズム学習においても重要なトピックです。本記事では、Javaでの再帰処理の基本から応用までを初心者向けに解説します。具体的な例を交えながら学んでいきましょう。

再帰とは？

再帰とは、メソッドが自分自身を呼び出すプログラミング技法のことです。再帰を使うことで、複雑な問題をシンプルに記述できます。

再帰処理の基本構造

再帰処理には以下の要素が必要です：

終了条件（ベースケース）: 再帰処理を停止させる条件です。
再帰ステップ: メソッドが自分自身を呼び出し、問題を小さく分割します。

public int recursiveMethod(int parameter) {
    if (終了条件) {
        return 結果; // ベースケース
    } else {
        return recursiveMethod(新しいパラメータ); // 再帰ステップ
    }
}

この構造を理解することで、再帰の仕組みが明確になります。

再帰アルゴリズムの例

1. 階乗の計算（Factorial）

階乗とは、1からその数までの整数をすべて掛け合わせた結果です。

実装例

public class Factorial {
    public static int factorial(int n) {
        if (n == 0) {
            return 1; // ベースケース: 0! = 1
        }
        return n * factorial(n - 1); // 再帰ステップ
    }

    public static void main(String[] args) {
        int number = 5;
        System.out.println(number + "! = " + factorial(number));
    }
}

出力結果

5! = 120

処理の流れ

factorial(5) を呼び出す。
5 * factorial(4) に展開。
最終的に 5 * 4 * 3 * 2 * 1 を計算。

2. フィボナッチ数列

フィボナッチ数列は、次のように計算されます：

最初の2つの値は 0 と 1。
それ以降の値は前の2つの値の合計。

実装例

public class Fibonacci {
    public static int fibonacci(int n) {
        if (n <= 0) {
            return 0; // ベースケース: 0番目は0
        } else if (n == 1) {
            return 1; // ベースケース: 1番目は1
        }
        return fibonacci(n - 1) + fibonacci(n - 2); // 再帰ステップ
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println(n + "番目のフィボナッチ数は: " + fibonacci(n));
    }
}

出力結果

10番目のフィボナッチ数は: 55

3. 配列の合計を計算

配列内のすべての要素を足し合わせるアルゴリズムです。

実装例

public class ArraySum {
    public static int sumArray(int[] arr, int n) {
        if (n <= 0) {
            return 0; // ベースケース
        }
        return arr[n - 1] + sumArray(arr, n - 1); // 再帰ステップ
    }

    public static void main(String[] args) {
        int[] data = {1, 2, 3, 4, 5};
        System.out.println("配列の合計は: " + sumArray(data, data.length));
    }
}

出力結果

配列の合計は: 15

4. 数値の逆順表示

与えられた数値を逆順に表示するアルゴリズムです。

実装例

public class ReverseNumber {
    public static void reverse(int n) {
        if (n < 10) {
            System.out.print(n); // ベースケース
            return;
        }
        System.out.print(n % 10); // 最後の桁を表示
        reverse(n / 10); // 残りの桁で再帰
    }

    public static void main(String[] args) {
        int number = 12345;
        System.out.print("逆順表示: ");
        reverse(number);
    }
}

出力結果

逆順表示: 54321

5. 最大公約数（GCD）の計算

2つの数の最大公約数を求める再帰アルゴリズムです。

実装例

public class GCD {
    public static int gcd(int a, int b) {
        if (b == 0) {
            return a; // ベースケース
        }
        return gcd(b, a % b); // 再帰ステップ
    }

    public static void main(String[] args) {
        int num1 = 56, num2 = 98;
        System.out.println("最大公約数は: " + gcd(num1, num2));
    }
}

出力結果

最大公約数は: 14

再帰処理のメリットと注意点

メリット

問題を簡潔に表現できる。
アルゴリズムの仕組みを直感的に理解しやすい。

注意点

終了条件の設定
終了条件を忘れると無限ループに陥ります。
パフォーマンスの低下
再帰処理はスタックメモリを使用するため、計算量が多いと効率が悪くなります（例: フィボナッチ数列）。
スタックオーバーフロー
再帰が深くなるとスタック領域を使い果たしてエラーが発生します。

反復処理への置き換え

再帰処理は便利ですが、すべての問題に適用する必要はありません。以下は、反復処理でフィボナッチ数列を計算する例です。

public class FibonacciIterative {
    public static int fibonacci(int n) {
        if (n <= 0) {
            return 0;
        } else if (n == 1) {
            return 1;
        }
        int a = 0, b = 1, result = 0;
        for (int i = 2; i <= n; i++) {
            result = a + b;
            a = b;
            b = result;
        }
        return result;
    }

    public static void main(String[] args) {
        int n = 10;
        System.out.println(n + "番目のフィボナッチ数は: " + fibonacci(n));
    }
}