再帰を使用した最大公約数を求めるアルゴリズム

最大公約数

「ユークリッドの互除法」というアルゴリズムがあります。それは、２つの整数 a, b (a >= b)があり、a = b*q + r ( q, r は整数 かつ b > r)。要するに割り算をします。そのあと a, b を b, r に置き換えて同じことを、r が０になるまで繰り返します。そのときの b が最大公約数です！

再帰

再帰とは、ある仕組みや定義などにそれ自身を含むものです。ここで扱うのは関数やメソッドの再帰です。うまく利用することでwhile文やfor文よりも効率的にコードを書くことができます。

実際のコード（Java）

Main.java

import java.util.Scanner;

class Main {

    static int d;

    public static void main(String[] args){
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();
        int r;
        if(x >= y){
            r = gcd(x,y);
        }else{
            r = gcd(y,x);
        }
        System.out.println(r);
    }

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

    }
}

gcd(a,b)というメソッドで再帰が利用されていることが分かります。

終わりに

記事をお読みいただきありがとうございました。最大公約数や再帰について理解できたでしょうか？感想お待ちしています！