STEP 5.2　（再帰バージョン)　

<問題>ユークリッドの互除法によって、２つの整数p, q の最大公約数を求めるプログラムを作成せよ。（ただし、p > q　とする）　どのような再帰呼び出しになっているか、プリント文を入れてみよう。

<実行結果> (自分がわかる出力を作ろう)
p,q (p > q)を入力してください
p = 512
q = 384

512と384の最大公約数を求める
gcd2( 512,  384) = gcd2( 384,  128)
p =  384, q =  128, r =    0
512と384の最大公約数は128である。


p,q (p > q)を入力してください
p = 91
q = 77

91と77の最大公約数を求める
gcd2(  91,   77) = gcd2(  77,   14)
gcd2(  77,   14) = gcd2(  14,    7)
p =   14, q =    7, r =    0
91と77の最大公約数は7である。

<ヒント>

• 関数 gcd2 (p, y) の呼び出し、と戻り値 きちんとまとめよう
  • 停止条件　pとqの最大公約数が（ズバっと）求まるときとは？
    • 条件
    • 戻り値
  • 再帰条件 pとqの最大公約数は、何と同じなのか。（問題は小さくなっているはず。やがて停止するはず
    • 条件
    • n-1次にするには
    • nの場合の戻り値は
    ）

解答例

#include <stdio.h>
int gcd2(int, int );

int main (void) {

    int p, q;

    printf("p,q (p > q)を入力してください \n");
    printf("p = ");
    scanf("%d", &p);
    printf("q = ");
    scanf("%d", &q);

    printf("\n%dと%dの最大公約数を求める\n", p, q);
    printf("%dと%dの最大公約数は%dである。\n",p, q, gcd2(p,q));

    return 0;

}


int gcd2(int p, int q) {

/* 適当なprintf文を入れてみよう */

   int r = p%q;    

   if (r ==0) {
       printf("p = %4d, q = %4d, r = %4d \n", p, q, r);
       return q ;
       }
   else  {
       printf("gcd2(%4d, %4d) = gcd2(%4d, %4d)\n", p, q, q, r);
       return gcd2(q, r);
   }

}