재귀 알고리즘 - 유클리드 호제법

정렬에 이어 처음으로 소개할 알고리즘은 재귀의 유클리드 호제법입니다.

---

1. 유클리드 호제법

유클리드 호제법(Euclidean Algorithm)은 두 정수의 최대공약수를 구하는 수학 알고리즘입니다. 두 정수의 최대공약수는 두 정수에서 큰 값을 작은 값으로 나누었을 때, 나머지가 0으로 나누어 떨어지는 값이 최대공약수입니다. 하지만, 보통 한 번의 계산으로는 나누어 떨어지지 않죠. 그래서 큰 값을 다시, 이전에 나온 나머지값으로 나누어 계산합니다. 이 과정을 반복하면 두 정수의 최대공약수를 구할 수 있습니다.

예) 30, 12
30/12 = 2 ... 6
30/6 = 5 ...0
따라서, 두 수의 최대 공약수는 5

최대공약수 구하는 과정을 보니 어디를 재귀적으로 처리해야할지 감이 잡히시나요?

 

 

2. 유클리드 호제법 구현

코드 자체는 간단합니다. 무려 네 줄만에 종료되는 알고리즘 구현입니다. 특히 주목해야할 부분은 두 수를 나눈 나머지가 0이 아닌 경우에 재귀호출을 하게 되는데, 이때 인수 전달과정에 주목해야합니다.

export const euclideanAlgorithm = (num1, num2) => {
    //첫 작동을 제외하고 num1은 큰 수, num2는 두 수를 나눈 나머지입니다.
    
    //나머지가 0이면 현재 몫이자 최대공약수인 num1 반환
    if (num2 == 0) {
        return num1;
    }
    //나머지가 0이 아니면
    else {
        //다시 재귀 호출
        //이때 인수로 num1에는 현재 나머지, num2로는 다시 나눈 나머지를 전달
        return euclideanAlgorithm(num2, num1 % num2);
    }
};

import {euclideanAlgorithm} from './study-code/recursive/euclidean-algorithm.js';

console.log(euclideanAlgorithm(30, 12));

방금 전에 직접 손으로 구한 최대공약수와 일치하죠?

---

https://github.com/Bam-j/algorithm-study/blob/main/study-code/recursive/euclidean-algorithm.js

GitHub - Bam-j/algorithm-study: 블로그 알고리즘 정리 포스트 코드 수록 + 코딩 테스트 코드 수록

export const euclideanAlgorithm = (num1, num2) => {
    if (num2 == 0) {
        return num1;
    }
    else {
        return euclideanAlgorithm(num2, num1 % num2);
    }
};