C++で再帰を使って最大公約数（GCD）を求めるプログラム

2つの数の最大公約数（GCD：Greatest Common Divisor）とは、その両方の数を割り切ることができる最大の整数のことです。

例として、63と42という2つの数を考えてみましょう。

63 = 7 × 3 × 3
42 = 7 × 3 × 2
したがって、63と42のGCDは 21

このように、共通する約数は「7」と「3」であり、その積である21が最大公約数となります。

ここでは、再帰（リカージョン）を使って2つの数のGCDを求めるC++プログラムを2つの方法で紹介します。

方法1：減算による再帰

1つ目の方法は、大きい方の数から小さい方の数を引く操作を再帰的に繰り返すアプローチです。これはユークリッドの互除法の原理に基づいています。

サンプルコード

#include<iostream>
using namespace std;
int gcd(int a, int b) {
    if (a == 0 || b == 0)
    return 0;
    else if (a == b)
    return a;
    else if (a > b)
    return gcd(a-b, b);
    else return gcd(a, b-a);
}
int main() {
    int a = 63, b = 42;
    cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
    return 0;
}

出力結果

GCD of 63 and 42 is 21

プログラムの解説

上記のプログラムでは、gcd()が再帰関数として機能しています。この関数は a と b の2つの引数を受け取り、以下のようなロジックで動作します。

• a または b が0の場合 → 関数は0を返します
• a と b が等しい場合 → 関数は a を返します
• a が b より大きい場合 → 引き算した値 (a-b) と b を使って自分自身を再帰的に呼び出します
• b が a より大きい場合 → a と (b-a) を使って再帰的に呼び出します

該当する部分のコードスニペットは以下の通りです。

int gcd(int a, int b) {
    if (a == 0 || b == 0)
    return 0;
    else if (a == b)
    return a;
    else if (a > b)
    return gcd(a-b, b);
    else return gcd(a, b-a);
}

方法2：剰余演算（%）による再帰

2つ目の方法は、モジュロ演算子（%）を使用するより効率的なアプローチです。こちらもユークリッドの互除法に基づいていますが、減算を繰り返す代わりに剰余を一度に計算するため、処理速度が大幅に向上します。

サンプルコード

#include <iostream>
using namespace std;
int gcd(int a, int b) {
    if (b == 0)
    return a;
    return gcd(b, a % b);
}
int main() {
    int a = 63, b = 42;
    cout<<"GCD of "<< a <<" and "<< b <<" is "<< gcd(a, b);
    return 0;
}

出力結果

GCD of 63 and 42 is 21

プログラムの解説

このプログラムでも gcd() は再帰関数です。a と b の2つの引数を持ち、次のように動作します。

• b が0になった場合 → 再帰の終了条件となり、a の値がそのまま main() 関数へ返されます
• b が0でない場合 → b と a % b（a を b で割った余り）を新しい引数として、自分自身を再帰的に呼び出します

該当するコードスニペットは以下の通りです。

int gcd(int a, int b) {
    if (b == 0)
    return a;
    return gcd(b, a % b);
}

まとめ

どちらの方法でも同じ結果が得られますが、減算方式は差が大きい場合に再帰呼び出しの回数が増えるのに対し、剰余演算方式は毎回余りを計算するため、より少ないステップで答えにたどり着きます。実務では方法2の剰余演算による再帰が一般的に推奨されます。