728x90
유클리드 호제법은 두 정수의 최대 공약수를 재귀적으로 구하는 방법입니다.
방식은 간단합니다.
100과 10의 최대 공약수를 구한다고 했을 때,
10,100%10이 다시 재귀로 함수 안에 들어갑니다.
그렇게 되면 100%10은 0이므로 첫번째 조건에 들어가고 10이 반환됩니다.
재귀 종료 조건은 큰 값을 작은 값으로 나누었을 때의 나머지가 0일 때이므로 첫 번째 조건은 n_2이==0이다.
그렇지 않으면 큰 값을 작은 값으로 나눈 나머지와 작은 값을 다시 함수에 넣지요.
static int gcd(int n_1, int n_2) {
if(n_2==0) {
return n_1;
}
else {
return gcd(n_2,n_1%n_2);
}
}
public static void main(String[] args) {
System.out.println(gcd(100,15));
System.out.println(gcd(100,10));
System.out.println(gcd(120,30));
System.out.println(gcd(140,7));
System.out.println(gcd(181,11));
}
728x90
'기타 > java 자료구조와 알고리즘' 카테고리의 다른 글
재귀 알고리즘 비재귀로 표현하기 (0) | 2021.01.03 |
---|---|
재귀 함수 알고리즘 예 하향식,상향식 분석하기 (0) | 2020.12.30 |
[JAVA]자바 재귀함수로 팩토리얼 계산기 만들기 (0) | 2020.12.28 |
자바 2 차원 배열 선언 및 초기화 (0) | 2020.12.27 |
[JAVA]소수 판별 메소드 (0) | 2020.12.25 |