【Python】再帰処理で2つの数の最大公約数（GCD）を求めるプログラム

はじめに

2つの数 a と b が与えられたとき、これらの最大公約数（GCD）を再帰的な手法で求めることを考えます。GCDを計算するには、古典的なユークリッドの互除法を利用します。

例えば、入力が a = 25、b = 45 の場合、出力は 5 になります。

アルゴリズムの手順

この問題を解くためには、以下の手順に従います。

• gcd() 関数を定義します。引数として a と b を受け取ります。
• a と b が等しい場合：
  • a を返します。
• a < b の場合：
  • gcd(b, a) を返します（引数の順序を入れ替えて再帰呼び出しします）。
• それ以外の場合：
  • gcd(b, a - b) を返します。

ユークリッドの互除法の仕組み

ユークリッドの互除法は、「2つの数の最大公約数は、大きい方から小さい方を引いても変化しない」という性質を利用したアルゴリズムです。この引き算の操作を繰り返していくと、最終的に2つの数が等しくなり、その時点の値が最大公約数となります。

実装例

以下のPythonコードを見て、理解を深めましょう。

def gcd(a, b):
    if a == b:
        return a
    elif a < b:
        return gcd(b, a)
    else:
        return gcd(b, a - b)

a = 25
b = 45
print(gcd(a, b))

入力

25, 45

出力

5

処理の流れを追ってみる

上記のコードがどのように動作するのか、a = 25、b = 45 の場合を順番に確認してみましょう。

• gcd(25, 45) → 25 < 45 なので gcd(45, 25) を呼び出す
• gcd(45, 25) → 45 > 25 なので gcd(25, 20) を呼び出す
• gcd(25, 20) → gcd(20, 5) を呼び出す
• gcd(20, 5) → gcd(5, 15) を呼び出す
• gcd(5, 15) → 5 < 15 なので gcd(15, 5) を呼び出す
• gcd(15, 5) → gcd(5, 10) を呼び出す
• gcd(5, 10) → gcd(10, 5) を呼び出す
• gcd(10, 5) → gcd(5, 5) を呼び出す
• gcd(5, 5) → 2つの数が等しくなったので 5 を返す

このように再帰呼び出しが繰り返され、最終的に GCD である 5 が得られます。

まとめ

ユークリッドの互除法を再帰関数として実装すると、ロジックがシンプルで直感的なコードになります。ただし、引き算ベースのこの実装は数値の差が大きい場合に再帰の回数が増えるという弱点があります。そのため、実務では「大きい数を小さい数で割った余り」を使う剰余演算（%）による改良版がよく用いられます。まずは本記事の基本形を理解した上で、発展的な実装にも挑戦してみてください。