Java リカーシブ アルゴリズムの徹底解説

1年 ago
陽, 向宇
1 minute

再帰アルゴリズムとは、自身が自身を呼び出すことで問題を解くアルゴリズムの一種です。Javaの再帰アルゴリズムでは、一般的に次の要素が含まれます。

  1. 基本ケース：再帰メソッドは直接に解が分かる基本ケースを持たなければならない。基本ケースでは再帰メソッドは自身を呼び出さず、結果を返す。
  2. 再帰呼び出し：再帰メソッドは、自分自身を呼び出すことで問題の一部を解決します。毎回の再帰呼び出しは、問題の規模を小さくし、基底ケースに達するまで続けます。
  3. 再帰パラメーター：再帰メソッドは再帰処理を制御するための1つ以上の引数を受け取ることができます。通常、再帰呼び出しが行われるたびに引数の値は変化します。

ここでは階乗を計算する例を用いて、再帰アルゴリズムの実装手順について詳しく説明します。

public class RecursionExample {
public static int factorial(int n) {
// 基本情况：n为0或1时，直接返回1
if (n == 0 || n == 1) {
return 1;
}
// 递归调用：调用factorial方法来计算n-1的阶乘，并将结果与n相乘
return n * factorial(n - 1);
}
public static void main(String[] args) {
int n = 5;
int result = factorial(n);
System.out.println("Factorial of " + n + " is " + result);
}
}

上記の例では、整数 n の階乗を計算するファクトリアルを静的メソッドとして定義しました。メソッド内部ではまず、n が 0 または 1 の場合は 1 を直接返却する基本ケースを確認します。そうでない場合は、ファクトリアルメソッドを呼び出して n – 1 の階乗を計算し、その結果に n を掛け合わせて最終的な結果を返します。

メインメソッド内では、factorialメソッドを呼び出して5の階乗を算出し、その結果をコンソールに出力しています。このプログラムを実行すると「Factorial of 5 is 120」が出力されます。

再帰アルゴリズムの基本的な考え方は、大きな問題をより小さな問題に分解し、再帰呼び出しによってそれらを解決し、最終的に全体的な問題の回答を得ることにある。ただし、再帰アルゴリズムはパフォーマンス上の問題を引き起こす可能性があることに注意する必要がある。それは、再帰のすべての呼び出しで新しいメソッドコールスタックがメモリ内に作成されるためである。したがって、再帰アルゴリズムを使用する場合、無限再帰が発生しないように注意し、再帰の規模は妥当な範囲で終えられるようにする必要がある。

bannerAds