修了試験 2019-07-28実施分 基本情報技術者試験 問8

解説

正解は2です。 関数fは、yが0になるまでf(y, x mod y)を再帰的に呼び出します。 これはユークリッドの互除法で、xとyの最大公約数を返します。 【計算】 f(775, 527)では、775 mod 527＝248なので、f(527, 248)を呼びます。 f(527, 248)では、527 mod 248＝31なので、f(248, 31)を呼びます。 f(248, 31)では、248＝31×8で余りは0なので、f(31, 0)を呼びます。 f(31, 0)はy＝0なので、xの値31を返します。 【選択肢別解説】 1：× 0は最後の呼出しのyの値で、返されるのはxの値です。 2：○ 再帰をたどると最終的にf(31, 0)となり、31が返されます。 3：× 248は1回目の余りで、まだ処理の途中の値です。 4：× 527は最初のyの値で、最大公約数ではありません。 【ポイント】 775＝31×25、527＝31×17なので、最大公約数が31であることも確かめられます。 「x mod yを使った再帰」はユークリッドの互除法と覚えておきましょう。