再帰を使って最大公約数（G.C.D）を求めるJavaプログラム

この記事では、再帰（リカージョン）を使用して2つの数値の最大公約数（G.C.D：Greatest Common Divisor）を求める方法について解説します。

再帰関数とは、特定の条件が満たされるまで自分自身を何度も呼び出す関数のことです。また、2つの数値の最大公約数とは、その両方を割り切る最大の整数のことを指します。

再帰とは

再帰とは、ある項目が自己相似的な形で繰り返されるプロセスのことです。プログラミング言語において、同じ関数の中でその関数自身を呼び出すことが許されている場合、これを「再帰呼び出し」と呼びます。

多くのプログラミング言語では、スタックを利用して再帰を実現しています。一般的に、ある関数（呼び出し元）が別の関数や自分自身（呼び出し先）を呼び出す際、実行制御は呼び出し元から呼び出し先へ移ります。この転送の過程で、データが呼び出し元から呼び出し先へ渡されることもあります。

入力と出力の例

以下に具体例を示します。

入力：

2つの数値を入力してください：24 と 36

出力：

24 と 36 の G.C.D は 12 です。

アルゴリズム

ステップ1 - 開始
ステップ2 - my_input_1、my_input_2、my_result の3つの変数を宣言する
ステップ3 - ユーザーから必要な値を読み込む／あらかじめ値を定義する
ステップ4 - 2つの整数を引数として受け取り、my_input_2 の値と my_input_1 % my_input_2 の値を返す再帰関数「CommonFactor」を定義する
ステップ5 - my_input_2 の値が0より大きい間、関数を再帰的に呼び出し続ける。結果を保存する
ステップ6 - 結果を表示する
ステップ7 - 終了

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

ここでは、ユーザーがプロンプトに対して入力した値をもとに計算を行います。

import java.util.Scanner;
public class GCD {
   public static void main(String[] args) {
      int my_input_1, my_input_2, my_result;
      System.out.println("必要なパッケージがインポートされました");
      Scanner my_scanner = new Scanner(System.in);
      System.out.println("リーダーオブジェクトが定義されました");
      System.out.print("1つ目の数値を入力してください : ");
      my_input_1 = my_scanner.nextInt();
      System.out.print("2つ目の数値を入力してください : ");
      my_input_2 = my_scanner.nextInt();
      my_result = CommonFactor(my_input_1, my_input_2);
      System.out.printf("%d と %d の G.C.D は %d です。", my_input_1, my_input_2, my_result);
   }
   public static int CommonFactor(int my_input_1, int my_input_2){
      if (my_input_2 != 0)
         return CommonFactor(my_input_2, my_input_1 % my_input_2);
      else
         return my_input_1;
   }
}

出力

必要なパッケージがインポートされました
リーダーオブジェクトが定義されました
1つ目の数値を入力してください : 24
2つ目の数値を入力してください : 36
24 と 36 の G.C.D は 12 です。

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

ここでは、整数値があらかじめプログラム内で定義されており、その値を取得してコンソールに表示します。

public class GCD {
   public static void main(String[] args) {
      int my_input_1, my_input_2, my_result;
      my_input_1 = 24;
      my_input_2 = 36;
      System.out.println("数値は " +my_input_1 +" と " +my_input_2 +" として定義されています");
      my_result = CommonFactor(my_input_1, my_input_2);
      System.out.printf("%d と %d の G.C.D は %d です。", my_input_1, my_input_2, my_result);
   }
   public static int CommonFactor(int my_input_1, int my_input_2){
      if (my_input_2 != 0)
         return CommonFactor(my_input_2, my_input_1 % my_input_2);
      else
         return my_input_1;
   }
}

出力

数値は 24 と 36 として定義されています
24 と 36 の G.C.D は 12 です。

まとめ

このように、ユークリッドの互除法を再帰関数として実装することで、簡潔なコードで最大公約数を求めることができます。剰余演算（%）を用いて引数を入れ替えながら再帰的に呼び出し、第2引数が0になった時点での第1引数が最大公約数となります。