再帰関数の値を互除法の手順で順にたどって求める
基本情報技術者試験 平成29年度春期 午前 問6 ／ アルゴリズムとプログラミング › アルゴリズム
過去問にチャレンジ
関数f(x，y)が次のとおり定義されているとき，f(775，527)の値は幾らか。ここで，x mod yはxをyで割った余りを返す。
- ア
0
- イ
31
- ウ
248
- エ
527
会話形式の解説
講師今回は再帰関数、つまり自分自身を呼び出す関数の問題です。注目してほしいのは、どこで呼び出しが止まるかという終了条件と、そのとき何を返すかの2点です。
受験者定義は、yが0ならxを返して、そうでなければf(y, x mod y)を呼ぶ、という形ですね。再帰は頭の中だけで追うと、どこまで進んだか分からなくなりがちです。
講師それなら、呼び出しを1回ずつ書き出しましょう。呼ぶたびに、前のyが新しいxに、xをyで割った余りが新しいyになります。最初のf(775, 527)では、yは0ですか。
受験者527なので0ではありません。775を527で割った余りは248なので、次はf(527, 248)です。
講師その調子です。248は1回目の余りとして出てきますが、この時点ではyが248で0ではないので、まだ終わりません。選択肢の248は、この途中の値です。
受験者続けると、527を248で割った余りは31なのでf(248, 31)、248を31で割ると割り切れるのでf(31, 0)になります。ここでyが0になりました。
講師では、終了条件のところで返すのはxとyのどちらでしょう。
受験者定義ではxを返すので31です。0はyの値なので、0を選ぶのは返す変数を取り違えたときですね。
講師そのとおりです。もう一つ確認すると、途中の呼び出しは返ってきた値をそのまま返すだけなので、最初のf(775, 527)の値も31になります。527は最初の呼び出しのyで、2回目にxの位置へ移ったあとも計算が続くので、答えにはなりません。
受験者整理すると、余りをとって引数を入れ替えていき、yが0になったときのxが答えなんですね。
講師はい。実はこの手順はユークリッドの互除法で、返る値は2つの数の最大公約数です。775は31×25、527は31×17で、25と17には1より大きい公約数がないので、31が最大公約数だと確かめられます。
受験者答えが出たら、両方の数を割り切れるかで検算すればよいのですね。終了条件で返す変数も必ず確認するようにします。
まとめ
この問題の関数は、yが0ならxを返し、そうでなければf(y, x mod y)を呼び出す再帰関数で、ユークリッドの互除法そのものです。f(775, 527)はf(527, 248)、f(248, 31)、f(31, 0)と進み、yが0になったときのxである31が返ります。途中の余りの248や、最初のyの527、終了時のyの0は、関数が返す値ではありません。31は775と527の最大公約数で、775=31×25、527=31×17から検算できます。
解答・解説
正解はイです
この問題のテーマ
再帰的に定義された関数を、引数が変わっていく順にたどって値を求める問題です。関数の中身は、ユークリッドの互除法で最大公約数を求める手順になっています。
解き方の考え方
関数fは、yが0ならxを返し、0でなければf(y, x mod y)を呼び出します。呼び出すたびに「前のyを新しいxにし、余りを新しいyにする」と入れ替えていき、yが0になったときのxが答えです。775 mod 527 = 248 なのでf(527, 248)になり、527 mod 248 = 31 なのでf(248, 31)、248 mod 31 = 0 なのでf(31, 0)になります。ここでy=0なのでxの31が返り、これがそのままf(775, 527)の値です。答えの31は正解イと一致します。
選択肢ごとの解説
- ×ア 00という値は、最後の呼び出しf(31, 0)の引数yのものです。定義では、yが0のときに返すのはyではなくxなので、0が答えになることはありません。
- ○イ 3131は、余りをとっていってyが0になったときの最後の呼び出しf(31, 0)で返るxの値です。途中の呼び出しは返ってきた値をそのまま返すだけなので、最初のf(775, 527)の値も31になります。
- ×ウ 248248は1回目の余り775 mod 527の値です。この時点ではyが248で0ではないので、f(527, 248)へ再帰が続きます。途中で出てくる値であり、関数が返す値ではありません。
- ×エ 527527は最初の呼び出しの引数yです。2回目の呼び出しではxの位置に移り、その後も計算が続くので、最終的に返る値にはなりません。
補足
答えが正しいかは、31で両方の数が割り切れるかで確かめられます。775 = 31 × 25、527 = 31 × 17 で、25と17には1より大きい公約数がないので、31は775と527の最大公約数です。
POINT
- 再帰関数は、終了条件（ここではy=0）にたどり着くまで、引数がどう変わるかを1回ずつ書き出すと確実に解けます。
- f(x, y) → f(y, x mod y) と入れ替えて、余りが0になったときに返るxが最大公約数です。これがユークリッドの互除法です。
- 終了条件で返すのがどの変数なのかを確認しましょう。0になるのはyですが、返すのはxです。