＝＝＝ 平成23年春 問6 ＝＝＝

---

平成23年春目次　 前の問題　 次の問題

---

問６

関数 f(x，y)が次のように定義されているとき，f(775，527)の値は幾らか。ここで，x mod yはxをyで割った余りを返す。

f(x, y): if y = 0 then return x else return f(y, x mod y)

ア　0　　　　イ　31　　　　ウ　248　　　　エ　527

解説

これは、自分自身を呼び出す再帰関数である。

■1回目の前半
f(775,527)つまり、x=775,y=527で呼び出される。
yは0でないので第1引数にはy（527）、第2引数にはxをyで割った余り248を指定してもう1回、fを呼び出す。
つまり、f(527,248)で呼出してそれがreturnした値を返そうとする。
まだ1回目の呼び出しは終わっていないことに注意

■2回目の前半
f(527,248)つまり、x=527,y=248で呼び出される。
yは0でないので第1引数にはy（248）、第2引数にはxをyで割った余り31を指定してもう1回、fを呼び出す。
つまり、f(248,31)で呼出してそれがreturnした値を返そうとする。

■3回目の前半
f(248,31)つまり、x=248,y=31で呼び出される。
yは0でないので第1引数にはy（31）、第2引数にはxをyで割った余り0を指定してもう1回、fを呼び出す。
つまり、f(31,0)で呼出してそれがreturnした値を返そうとする。

■4回目
f(31,0)つまり、x=31,y=0で呼び出される。
yは0なので、31を返す。
ここで、4回目に呼ばれたfは終了して、3回目の呼出しに戻る。


■3回目の後半
f(31,0)が返した値（31）を呼び出し元に返し、終了。

■2回目の後半
f(248,31)が返した値（31）を呼び出し元に返し、終了。

■1回目の後半
f(527,248)が返した値（31）を呼び出し元に返し、終了。

これで結局　f(775,527)の呼び出しは31を返したことになる。

答

イ