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

はじめに

数学において、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

Skills Graph

入力数値の読み取り

まず、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の計算が必要な数学的な問題の解決に使用できます。