再帰関数 f(775, 527) の値を求める
今回は、再帰関数 の問題です。
関数の中で自分自身を呼び出しているので、最初は難しく見えますが、やっていることはシンプルです。
この関数は、2つの整数の 最大公約数 を求める処理です。
問題
関数 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この関数がしていること
この関数 f(x, y) は、次のルールで動きます。
y が 0 のとき
→ x を答えとして返す
y が 0 ではないとき
→ f(y, x mod y) をもう一度計算するポイントは、次の部分です。
f(y, x mod y)これは、次のように考えます。
新しい x = 今の y
新しい y = 今の x を 今の y で割った余りつまり、x と y を入れ替えながら、余りを使って数を小さくしていきます。
mod とは何か
x mod y は、x を y で割ったときの 余り です。
例えば、
775 mod 527は、
775 ÷ 527 = 1 余り 248なので、
775 mod 527 = 248です。
この「余り」を次の関数呼び出しに使います。
実際に f(775, 527) を計算する
最初は、次の状態です。
f(775, 527)このとき、y = 527 です。
y は0ではないので、次の式を使います。
f(x, y) = f(y, x mod y)したがって、
f(775, 527)
= f(527, 775 mod 527)775 mod 527 を計算します。
775 ÷ 527 = 1 余り 248よって、
f(775, 527)
= f(527, 248)2回目の計算
次は、
f(527, 248)です。
このとき、y = 248 です。
まだ0ではないので、同じルールを使います。
f(527, 248)
= f(248, 527 mod 248)527 mod 248 を計算します。
527 ÷ 248 = 2 余り 31したがって、
f(527, 248)
= f(248, 31)3回目の計算
次は、
f(248, 31)です。
このとき、y = 31 です。
まだ0ではないので、同じルールを使います。
f(248, 31)
= f(31, 248 mod 31)248 mod 31 を計算します。
248 ÷ 31 = 8 余り 0したがって、
f(248, 31)
= f(31, 0)y が0になったら終了
最後に、
f(31, 0)になりました。
このとき、y = 0 です。
問題文の定義では、
if y = 0 then return xなので、x を返します。
このときの x は 31 です。
f(31, 0) = 31計算の流れをまとめる
全体の流れは、次のようになります。
f(775, 527)
= f(527, 775 mod 527)
= f(527, 248)
= f(248, 527 mod 248)
= f(248, 31)
= f(31, 248 mod 31)
= f(31, 0)
= 31したがって、答えは
31です。
正解は、
イ 31です。
この関数の正体はユークリッドの互除法
この関数は、ユークリッドの互除法 です。
ユークリッドの互除法は、2つの整数の最大公約数を求める方法です。
今回であれば、
775 と 527 の最大公約数を求めています。
実際に割り算の余りを見ると、
775 ÷ 527 = 1 余り 248
527 ÷ 248 = 2 余り 31
248 ÷ 31 = 8 余り 0余りが0になったときの割る数が 31 なので、最大公約数は 31 です。
初心者がつまずきやすいポイント
この問題で難しく感じる理由は、次の部分です。
return f(y, x mod y)ここで、x と y が入れ替わります。
例えば、
f(775, 527)の次は、
f(527, 248)になります。
ここで、
527 は、前の y
248 は、775 mod 527 の余りです。
つまり、毎回、
前の y が、次の x になる
前の x mod 前の y が、次の y になると考えると追いやすくなります。
解き方のコツ
このタイプの問題は、頭の中だけで追うと混乱しやすいです。
次のような表を書きましょう。
現在の関数 x mod 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 mod 31 = 0 f(31, 0)
f(31, 0) y = 0 31を返す再帰関数の問題では、
今の x は何か
今の y は何か
x mod y は何か
次に呼び出す関数は何かを1行ずつ整理することが大切です。
まとめ
問題3-9の関数 f(x, y) は、再帰を使って最大公約数を求める関数です。
今回の計算は、次のように進みます。
f(775, 527)
→ f(527, 248)
→ f(248, 31)
→ f(31, 0)
→ 31したがって、正解は
イ 31です。
この問題では、mod の余りを計算しながら、x と y を入れ替えていく流れを表で追うのが一番確実です。