[Java] 재귀 | 유클리드 호제법(최대 공약수 구하기)

 

유클리드 호제법

22와 8의 최대 공약수는 위와 같이 정사각형으로 모두 나누어 떨어졌을 때, 가장 작은 길이인 2가 된다. 

 

큰 수를 작은 수로 나누었을 때 나머지가 0이면 작은 수가 최대공약수이다.
나머지가 0이 아니면 나머지와 작은 값으로 다시 반복

---

코드

public class Euclidean {
    int euclidean(int x, int y){
        int m, n;
        if(x>y){
            m = x;
            n = y;
        }
        else {
            m = y;
            n = x;
        }
        if(m%n == 0){
            return  n;
        }

        else {
            int g = m%n;
            System.out.printf("(%d, %d)", n, g);
            return euclidean(n, g);
        }

    }
}

public class StackMain {
    public static void main(String[] args) {

        Euclidean euclidean = new Euclidean();
        int x = euclidean.euclidean(22, 8);
        System.out.println(x);
    }
}

---

실행결과