ユークリッドの互除法（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のような組み込みが用意されています。実務ではそちらを使いますが、中で起きていることは今回書くものと同じです。
演習で使う書き方
例として 35 と 14 は、(35, 14) → (14, 7) → (7, 0) と縮みます。最後の組は割り算をせずに答えを決めます。% は余りを求めます。演習ではこの停止条件と、次の組を渡す呼び出しを自分で書きます。
要件
- 余りが 0 の停止条件と、余りへの再帰を自分で実装する
- 関数名と引数、入力と戻り値の形を保つ。説明つきの準備部分を使い、TODO の仮の処理を置き換える