データ構造とアルゴリズム
関数 f(x, y) を「y が0なら x を返し、そうでなければ f(y, x mod y) を返す」と定義する。f(84, 36) を呼んだときの戻り値と、f が呼ばれる回数(最初の呼び出しを含む)の組はどれか。
- A戻り値12、呼ばれる回数3回
- B戻り値12、呼ばれる回数4回
- C戻り値6、呼ばれる回数3回
答えと解説を見る
正解：A. 戻り値12、呼ばれる回数3回
f(84, 36) は 84 mod 36 = 12 なので f(36, 12) を呼び、36 mod 12 = 0 なので f(12, 0) を呼び、y が0なので12を返します。呼び出しは f(84, 36)、f(36, 12)、f(12, 0) の3回で、これはユークリッドの互除法による最大公約数の計算です。この関数は再帰呼び出しの結果をそのまま返す末尾再帰なので、コンパイラが末尾呼び出しの最適化を行えばループに変換でき、呼び出しが深くなってもスタックを使い続けません。
- A. 正しい。f(84, 36)→f(36, 12)→f(12, 0) の3回で、84と36の最大公約数12を返します。
- B. f(12, 0) で y が0になった時点で終わるので、4回目の呼び出しはありません。
- C. 84と36の最大公約数は12です(84 = 12×7、36 = 12×3)。