関数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)
正答2
解説
正解は2です。
この問題は、再帰的に定義された関数をたどる力を問うています。
この関数fは、ユークリッドの互除法により2数の最大公約数を求める手続です。
yが0になったときのxが答えとして返されます。
【計算】
f(775, 527)では、775を527で割った余りは248なので、f(527, 248)を呼び出します。
f(527, 248)では、527を248で割った余りは31なので、f(248, 31)を呼び出します。
f(248, 31)では、248を31で割った余りは0なので、f(31, 0)を呼び出します。
f(31, 0)はyが0なので、xの値31を返します。
【選択肢別解説】
1：× 0は最後の呼出しでyに入る値であり、返される値ではありません。
返されるのはそのときのxの31です。
2：○ 再帰呼出しをたどると、yが0になった時点のxは31です。
775と527の最大公約数も31です。
3：× 248は最初の余りであり、まだ再帰の途中の値です。
4：× 527は最初の引数yの値であり、答えではありません。
【ポイント】
ユークリッドの互除法は、「大きい数を小さい数で割った余り」で置き換える操作を余りが0になるまで繰り返します。
検算として、775＝31×25、527＝31×17となり、31が公約数であることを確認できます。