이해를 돕기 위해서 두 가지 예를 유클리드의 방식으로 풀어 보겠습니다. 하나는 60과 24의 최대공약수를 구하는 것이고, 다른 하나는 81과 27의 최대공약수를 구하는 것입니다.

 

gcd(60, 24) = gcd(24, 60 % 24) = gcd(24, 12) = gcd(12, 24 % 12) = gcd(12, 0) = 12

gcd(81, 27) = gcd(27, 81 % 27) = gcd(27, 0) = 27

 

신기하게도 최대공약수 문제가 몇 번만 계산했을 뿐인데 풀리는 것을 확인할 수 있습니다. 그런데 풀이 과정을 유심히 살펴보면 어떤 두 수의 최대공약수를 구하기 위해 다시 다른 두 수의 최대공약수를 구하고 있는 것을 알 수 있습니다. 이것이 바로 ‘재귀 호출’로 이 문제를 풀 수 있다는 힌트입니다.

이 문제는 a와 b의 최대공약수를 구하기 위해서 (a, b)보다 좀 더 작은 숫자인 (b, a % b)의 최대공약수를 구하는 과정을 이용하는 전형적인 재귀 호출 문제입니다(좀 더 작은 값으로 자기 자신을 호출합니다).

그렇다면 재귀 호출이 무한히 반복되지 않도록 하는 데 필요한 종료 조건은 무엇일까요? 바로 ‘어떤 수와 0의 최대공약수는 자기 자신’이라는 성질입니다. 이 성질이 종료 조건을 만들어 냅니다. 즉, b가 0이면 재귀 호출을 멈추고 결과를 돌려줍니다.

유클리드 알고리즘을 이용해 최대공약수를 구하는 프로그램을 만들면 다음과 같습니다.