再帰を使った最大公約数の求め方

はじめに

数学において、2 つの数の最大公約数（GCD：Greatest Common Divisor）は、2 つの数を割り切って余りを残さない最大の正の整数として一般的に定義されます。この実験では、再帰を使って 2 つの数の GCD を見つける C プログラムを書く方法を学びます。

注：コーディングを練習し、gcc を使ってコンパイルと実行する方法を学ぶには、自分で~/project/main.cファイルを作成する必要があります。

cd ~/project
## main.cを作成する
touch main.c
## main.cをコンパイルする
gcc main.c -o main
## mainを実行する
./main

入力数値の読み取り

まず、2 つの整数の入力数値をユーザーから取得して、それらの GCD を求める必要があります。入力を読み取るためにscanf()関数を使用します。

#include<stdio.h>

int main()
{
    int a, b;
    printf("Enter two numbers to find GCD of: \n");
    scanf("%d%d", &a, &b);
    // コードの残り部分
    return 0;
}

GCD を求める再帰関数の定義

2 つの入力数値の GCD を求めるために再帰関数を使用します。再帰関数は 2 つの整数型のパラメータを持ちます。2 つの数が同じ値になるまで関数自身を呼び続け、その値を GCD として返します。

int find_gcd(int x, int y)
{
    if(x == y)
        return x;
    if(x > y)
        return find_gcd(x-y, y);
    return find_gcd(x, y-x);
}

メイン関数から再帰関数を呼び出す

このステップでは、再帰関数に 2 つの入力数値（a と b）を渡して呼び出します。再帰関数の返り値を整数型の変数（gcd）に格納します。

int gcd = find_gcd(a, b);
printf("GCD of %d and %d is: %d\n", a, b, gcd);

完全なサンプルコード

#include <stdio.h>

// 再帰関数を宣言する
int find_gcd(int, int);

int main()
{
    int a, b, gcd;
    printf("Enter two numbers to find GCD of: \n");
    scanf("%d%d", &a, &b);
    gcd = find_gcd(a, b);
    printf("GCD of %d and %d is: %d\n", a, b, gcd);
    return 0;
}

// 関数を定義する
int find_gcd(int x, int y)
{
    if(x == y)
        return x;
    if(x > y)
        return find_gcd(x-y, y);
    return find_gcd(x, y-x);
}

まとめ

この実験では、再帰を使って 2 つの数の最大公約数（GCD）を求める C 言語のプログラムを書く方法を学びました。関数が修正された入力パラメータを持って自身を呼び出し、ベースケースに達するまで GCD を計算する再帰関数を利用しました。このプログラムは、2 つの数の GCD の計算が必要な数学的な問題の解決に使用できます。