[Toy] 유클리드 호제법

## 유클리드 호제법

 

 - 두 수의 최대공약수를 구하는 알고리즘으로, 두 수가 상대방 수를 나누어서 원하는 수를 얻게 된다.

 - n1 > n2 인 경우에 n1을 n2로 나눈 나머지를 r이라고 한다면 n1, n2의 최대공약수는 n2, r의 최대공약수와 같다.

 - n2와 r을 다시 원래의 n1, n2의 자리에 넣어 n1을 n2로 나눈 나머지를 r이라고 하면, n1, n2의 최대공약수는 n2, r의 최대공약수와 같게 된다.

 - 위의 과정을 n1을 n2로 나눈 나머지(아래 코드의 n2자리에 들어오는 수)가 0일 때까지(두 수가 나누어 떨어질 때까지) 반복했을 때, n1자리에는 처음 n1, n2의 최대공약수가 있게 된다.

// n1 > n2
const gcd = (n1, n2) => {
  return n2 === 0 ? n1 : gcd(n2, n1 % n2);
};

 

위 과정을 재귀적으로 나타내었다.

 

 

참고:

https://ko.wikipedia.org/wiki/%EC%9C%A0%ED%81%B4%EB%A6%AC%EB%93%9C_%ED%98%B8%EC%A0%9C%EB%B2%95