【初心者向け】Javaで再帰を使って階乗を求めるプログラムの書き方

本記事では、再帰(リカージョン)を使用して数の階乗を求めるJavaプログラムの作成方法を詳しく解説します。

階乗とは何か

階乗(factorial)とは、ある数とそれ以下のすべての正の整数を掛け合わせた値のことです。階乗は0より大きい自然数に対して定義される関数であり、その記号は数字の後に付ける「!(エクスクラメーションマーク)」で表されます。たとえば5の階乗は「5!」と書き、5 × 4 × 3 × 2 × 1 = 120となります。

再帰とは何か

再帰関数とは、特定の条件が満たされるまで自分自身を繰り返し呼び出す関数のことです。再帰とは、自己相似的な形で処理を繰り返す手法を指します。プログラミングにおいて、関数の中から同じ関数自身を呼び出すことを再帰呼び出しと呼びます。

多くのプログラミング言語では、再帰はスタック(stack)によって実装されています。一般的に、ある関数(呼び出し元)が別の関数や自分自身(呼び出し先)を呼び出すと、実行の制御は呼び出し元から呼び出し先へ移ります。この際、引数などのデータも呼び出し元から呼び出し先へ渡されます。

実行例

入力:

Enter the number : 7

出力:

The factorial of 7 is 5040

アルゴリズム

Step 1 - 開始
Step 2 - 整数型の変数「my_input」と、long型の変数「my_result」を宣言する
Step 3 - ユーザーから必要な値を読み込む(または値を直接定義する)
Step 4 - 整数を引数に受け取り、入力値が1になるまで「入力値 × 直前の数」という積を返す再帰関数「factorial」を定義する
Step 5 - 再帰関数を呼び出し、「my_input」を引数として渡す。戻り値を変数に格納する
Step 6 - 結果を表示する
Step 7 - 終了

例1:ユーザーからの入力を受け取る場合

この例では、Scannerクラスを使ってユーザーが入力した値を取得します。オンラインのコンパイル環境でも実際に動作を確認できます。

import java.util.Scanner;
public class Factorial {
    public static void main(String[] args) {
        int my_input ;
        long my_result;
        System.out.println("Required packages have been imported");
        Scanner my_scanner = new Scanner(System.in);
        System.out.println("A reader object has been defined ");
        System.out.print("Enter the number : ");
        my_input = my_scanner.nextInt();
        my_result = factorial(my_input);
        System.out.println("The factorial of " + my_input + " is " + my_result);
    }
    public static long factorial(int my_input){
      if (my_input >= 1)
         return my_input * factorial(my_input - 1);
      else
         return 1;
   }
}

実行結果:

Required packages have been imported
A reader object has been defined
Enter the number : 7
The factorial of 7 is 5040

例2:値をあらかじめ定義しておく場合

この例では、整数値を事前に定義しておき、その値を取得してコンソールに表示します。

public class Factorial {
    public static void main(String[] args) {
        int my_input ;
        long my_result;
        my_input = 7;
        System.out.println("The number is defined as " +my_input);
        my_result = factorial(my_input);
        System.out.println("The factorial of " + my_input + " is " + my_result);
    }
   public static long factorial(int my_input){
      if (my_input >= 1)
         return my_input * factorial(my_input - 1);
      else
         return 1;
   }
}

実行結果:

The number is defined as 7
The factorial of 7 is 5040

ポイントまとめ

• 再帰関数には必ず終了条件(ベースケース)が必要です。この例では「my_input >= 1」が満たされなくなった時点で1を返し、再帰が停止します。
• 戻り値にlong型を使用することで、int型よりも大きな階乗の値を扱えます。ただし、long型で表現できるのは概ね20!(約243京)までである点に注意してください。
• 再帰呼び出しが深くなりすぎるとStackOverflowErrorが発生する可能性があるため、大きな数を扱う場合はループによる実装も検討しましょう。