整数x，y（x＞y≧0）に対して，次のように定義された関数F(x,y)がある。
F(231,15)の値は幾らか。
ここで，x mod yはxをyで割った余りである。
F(x,y) = x （y＝0のとき）
F(x,y) = F(y, x mod y) （y＞0のとき）
正答2
解説
正解は2です。
この関数は、yが0になるまでF(y, x mod y)を繰り返す再帰関数です。
これはユークリッドの互除法であり、xとyの最大公約数を求めます。
【計算】
F(231,15)では、231 mod 15＝6なのでF(15,6)になります。
F(15,6)では、15 mod 6＝3なのでF(6,3)になります。
F(6,3)では、6 mod 3＝0なのでF(3,0)になります。
F(3,0)はy＝0なので、値はx＝3です。
【選択肢別解説】
1：× 2は231の約数ではないので、最大公約数にはなりません。
2：○ 上の計算のとおり、F(231,15)＝3です。
231＝3×7×11、15＝3×5なので、最大公約数3と一致します。
3：× 5は15の約数ですが、231は5で割り切れません。
4：× 7は231の約数ですが、15は7で割り切れません。
【ポイント】
「F(y, x mod y)」の形を見たら、ユークリッドの互除法を思い出しましょう。
素因数分解で最大公約数を求めて、答えを検算することもできます。