修了試験 2021-06-13実施分 基本情報技術者試験 問9

解説

正解は2です。 再帰的に定義された関数の値を求める問題です。 この関数は、ユークリッドの互除法で2つの数の最大公約数を求めるものです。 【計算】 f(775, 527)：775 mod 527 ＝ 248 なので、f(527, 248) を呼びます。 f(527, 248)：527 mod 248 ＝ 31 なので、f(248, 31) を呼びます。 f(248, 31)：248 mod 31 ＝ 0 なので、f(31, 0) を呼びます。 f(31, 0)：y＝0 なので、x の値31を返します。 【選択肢別解説】 1：× 0は最後の呼出しで y に入る値です。 y＝0 のときに返すのは x の値なので、0にはなりません。 2：○ 互除法をたどると31が返ります。 775＝31×25、527＝31×17であり、31は最大公約数です。 3：× 248は1回目の余りです。 途中の値であり、最終的な戻り値ではありません。 4：× 527は最初の引数 y の値です。 関数を一度も展開していない値なので誤りです。 【ポイント】 f(x, y)＝f(y, x mod y) を余りが0になるまで繰り返すと、最大公約数が求まります。 基本情報技術者試験では、再帰関数をトレースする問題として頻出です。