再帰関数の値
関数 f(x, y) が次のように定義されているとき，f(156, 60) の値はどれか。ここで，x mod y は x を y で割った余りを表す。 f(x, y)：y = 0 のとき x，それ以外のとき f(y, x mod y)
- ア6
- イ24
- ウ12
- エ36
正解と解説を見る
正解 ウ
この問題の基礎知識
- 再帰関数の値は，終了条件に達するまで，定義に従って引数を置き換えながら呼出しを順にたどって求める。
- x mod y は x を y で割った余りであり，x と y が正の整数なら 0 以上 y 未満の値になる。
- ユークリッドの互除法は，「x と y の最大公約数は，y と x mod y の最大公約数に等しい」ことを繰り返し用い，余りが 0 になったときの除数を最大公約数とする方法である。
ア6
6 は 156 と 60 の公約数の一つではあるが，この関数が返す値ではない。f は最大公約数を求めるユークリッドの互除法であり，値は 12 になる。
イ24
24 は計算の途中で現れる余り（60 mod 36）であり，最終的な値ではない。さらに f(24, 12) を経て f(12, 0)＝12 まで再帰が続く。
ウ12正解
f(156, 60)→f(60, 36)→f(36, 24)→f(24, 12)→f(12, 0) と再帰し，y＝0 となったときの x である 12 が値となる。これは 156 と 60 の最大公約数である。
エ36
36 は最初の余り（156 mod 60）であり，最終的な値ではない。y が 0 になるまで再帰が続くので，値は 12 となる。
検証用の出典出典照合済み
D. E. Knuth, The Art of Computer Programming, Vol. 2: Seminumerical Algorithms照合の根拠（1 件）
- ウ（正解）: 値 12 は 156 と 60 の最大公約数であり，ア 6 は公約数だが最大ではない
The largest positive integer that divides each of two or more positive integers without a remainder.
NIST CSRC Glossary（greatest common divisor，出典 NIST SP 800-56B Rev. 2） · greatest common divisor（新しいタブで開きます）
検算: 156 mod 60＝36，60 mod 36＝24，36 mod 24＝12，24 mod 12＝0 より f(156,60)→f(60,36)→f(36,24)→f(24,12)→f(12,0)＝12。36 と 24 は途中の余り。156＝2²·3·13，60＝2²·3·5 で gcd＝12 とも一致