Recursive Algorithm - GCD(최대공약수)

GCD

- 유클리드 호제법/알고리즘(Euclidean Algorithm) : 두 수의 “최대공약수(GCD)”를 찾기 위한 알고리즘

 

- 큰 수를 작은 수로 나누어 떨어지게 하여 수를 반복적으로 취하여 나머지 0이 될 때까지 작동하는 방법 / 작은 수가 최대공약수

---

Java예시

 

- m = 작은 수, n = 큰 수를 입력으로 받고, n=0이 될 때까지 recursive 실행

 

- 큰 수와 작은수를 큰 수로 나눈 나머지를 구하는 연산을 계속 하면서, m의 값을 갱신

 

- main함수에서 실행한 결과

---

C예시 - 추가 예정