유클리드 호제법으로 최대공약수 구하기

* 유클리드 호제법 개념 참고

재귀 호출을 이용하여 유클리드 호제법 알고리즘을 구현하였다.
두 수를 서로 나눈 나머지와 두 수중의 하나의 수는 서로 최대 공약수인 점을 이용하여,
나머지와 하나의 수를 계속 나누어 가다보면 나머지가 0이 되는 시점에서 나누어지는 수를 리턴한다.

public class EuclidGCD {
    //유클리드 호제법 알고리즘을 이용합니다.
    //정수 x,y의 최대 공약수를 구하여 반환합니다.
    static int gcd(int x, int y) {
        if(y == 0)
            return x;
        else
            return gcd(y, x % y);
    }
    public static void main(String[] args) {
        Scanner sc = new Scanner(System.in);
        int x = sc.nextInt();
        int y = sc.nextInt();

        System.out.println("최대 공약수는 " + gcd(x, y) + "입니다.");
    }
}