【C言語】再帰関数を使って2つの整数の最大公約数（GCD）を求める方法

問題

C言語において再帰関数を使用し、与えられた2つの整数の最大公約数（GCD：Greatest Common Divisor）を求めます。

解決策

再帰関数を用いて2つの整数の最大公約数を求めるには、「ユークリッドの互除法」が利用できます。これは「2つの数のGCDは、大きい方の数を小さい方の数で割った余りと、小さい方の数とのGCDに等しい」という性質を応用した手法です。この計算を余りが0になるまで再帰的に繰り返すことで、GCDを効率よく求めることができます。

アルゴリズム

再帰関数を使って2つの整数のGCDを求めるためのアルゴリズムは、以下の手順に従います。

ステップ1 − 再帰関数を定義します。

ステップ2 − 2つの整数 a と b を入力として読み込みます。

ステップ3 − 再帰関数を呼び出します。

a. もし j > i ならば、引数を入れ替えて GCD(j, i) を返します。
b. もし j == 0 ならば、i を返します。
c. それ以外の場合は、GCD(j, i % j) を返します。

フローチャート

上記アルゴリズムの処理の流れを、以下のフローチャートに示します。

サンプルプログラム

以下は、再帰関数を使用して2つの整数の最大公約数（GCD）を求めるCプログラムです。

#include<stdio.h>
#include<math.h>
unsigned int GCD(unsigned i, unsigned j);
int main(){
   int a,b;
   printf("Enter the two integers: \n");
   scanf("%d%d",&a,&b);
   printf("GCD of %d and %d is %d\n",a,b,GCD(a,b));
   return 0;
}
/* 再帰関数 */
unsigned int GCD(unsigned i, unsigned j){
   if(j>i)
      return GCD(j,i);
   if(j==0)
      return i;
   else
      return GCD(j,i%j);
}

実行結果

上記のプログラムをコンパイルして実行すると、以下のような結果が出力されます。

Enter the two integers: 4 8
GCD of 4 and 8 is 4

プログラムの解説

入力例「4 8」の場合、処理は次のように進みます。

まず GCD(4, 8) が呼び出されると、j > i であるため引数が入れ替えられ、GCD(8, 4) となります。次に 8 % 4 = 0 となるため、GCD(4, 0) が呼び出されます。ここで j == 0 となるため、最終的に 4 が返されます。このように、再帰呼び出しがベースケース（j == 0）に到達するまで繰り返されることで、正しいGCDが求まります。