ユークリッドの互除法（GCD）
12 と 18 の最大公約数は 6。これを求める最古の方法がユークリッドの互除法です。紀元前 300 年ごろに書かれた手順が、今でも最速の部類で動きます。今回の主題は「なぜこれが必ず終わるのか」です。
止め忘れると、0 で割って落ちる
互除法は割り算の余りを使い続けます。まず % の振る舞いを確かめておきます。
Python
17 % 5 # 2 余りは、割る数より必ず小さい
9 % 3 # 0 割り切れたら 0
4 % 9 # 4 割る数のほうが大きいと、そのまま残る
7 % 0 # ZeroDivisionError最後の行が今回の落とし穴です。余りを繰り返し取っていくと、いつか必ず 0 が現れます。そこで止めると書き忘れると、次の呼び出しで 0 を割る数として渡してしまい、延々と回り続ける前にゼロ除算で落ちます。
止まらない再帰が、必ずしも再帰のエラーで落ちるとは限らない、という例です。ゼロ除算のエラーだけを見ると、割り算の書き方を間違えたように見えてしまいます。実際に足りないのは、止める条件のほうです。エラーの名前だけで原因を決めつけないでください。
余りは、必ず割る数より小さい
なぜ必ず 0 に届くのか。理由は % の 1 行目に書いた性質にあります。余りは 0 以上で、割る数より必ず小さい。だから次に持っていく数は、今の割る数より確実に小さくなります。値が同じところで足踏みすることはありません。
整数が真に小さくなり続け、下は 0 で止まっている。そうであれば、有限回で必ず 0 に着きます。境界を 1 つずつ手で追わなくても、この性質だけで「止まる」と言い切れるのが互除法の気持ちのよいところです。
48 と 18 で余りを取り続けると、こう縮みます。
プレーンテキスト
48 を 18 で割った余りは 12
18 を 12 で割った余りは 6
12 を 6 で割った余りは 03 回で 0 に着きました。1 から順に共通の約数を試す方法だと最悪で 18 回かかるので、桁が大きくなるほど差が開きます。数が 10 桁あっても数十回で終わる速さです。
大きい数を先に渡さなくてよい
小さいほうを先に渡してしまったら、と心配になりますが、直す必要はありません。% の 3 行目のとおり、割る数のほうが大きいと余りは元の数のままです。その結果、次の呼び出しで 2 つの引数が入れ替わり、大きいほうが先に来た状態へ自動で補正されます。
余分に 1 段降りるだけで、答えは変わりません。呼ぶ前に大小を並べ替える処理は要らない、ということです。テストには 12 と 18 の両方の順番が入っていますが、どちらも同じ答えになります。
もう一つ、片方が片方の倍数のときも特別扱いは要りません。100 と 25 なら 1 回目の余りがいきなり 0 になるので、そのまま止まります。境界に見えるケースが、実は同じ道を通っている。互除法が 2300 年生き残っているのは、この取りこぼしの無さのおかげです。
多くの言語には
math.gcdのような組み込みが用意されています。実務ではそちらを使いますが、中で起きていることは今回書くものと同じです。
要件
- 関数
gcd(a, b)を実装し、最大公約数を整数で返す - for / while / 組み込み math.gcd を使わず、必ず再帰で実装する
- 基底ケースは b == 0 のとき a を返す
入出力例
gcd(12, 18) → 6
gcd(18, 12) → 6
gcd(7, 13) → 1
gcd(100, 25) → 25
gcd(48, 36) → 12
gcd(1, 1) → 1ヒント
