最大公約数・最小公倍数を求める(ユークリッドの互除法)

このレッスンでは、ユークリッドの互除法を使って最大公約数と最小公倍数を求める方法を学び、再帰関数の基本を体験することを目標にします。「JavaScript 最大公約数 求め方」「再帰関数 とは」で調べている方向けです。

ユークリッドの互除法は、2つの数の最大公約数(GCD)を効率よく求める古代からのアルゴリズムです。「大きい方を小さい方で割った余りで、また同じ計算を繰り返す」を余りが0になるまで続けます。この「自分自身を呼び出し続ける」書き方を再帰関数と呼びます。

サンプルコードでは、gcd(a, b)関数がb === 0になるまでgcd(b, a % b)という形で自分自身を呼び出し続けています。最小公倍数(LCM)は、最大公約数を使った計算式(a * b) / gcd(a, b)で求められる、という2つのアルゴリズムのつながりも確認してみましょう。

初心者がよくつまずくのが、再帰関数には必ず「終わる条件」が必要だという点です。b === 0のような終了条件がないと、関数が自分自身を無限に呼び出し続けてしまい、エラーになります。再帰関数を書くときは、まず「どうなったら終わるか」を最初に考える習慣をつけましょう。

再帰関数の練習題材としても非常によく使われる、数学とプログラミングの両方の基礎が詰まった有名なアルゴリズムです。計算式そのものはシンプルなので、再帰関数の考え方を学ぶ入門としても最適な題材です。