유클리드 공식을 통한 G.C.D. 구하기

재귀 호출을 활용한 소스 코드

유클리드 방식을 이용해 재귀(recursion)호출이 이루어진다.

이전 섹션에서 본인이 작성한 코드보다 절반 가량 줄인 분량의 소스 코드를 보고 허탈했었는데, 그 소스 코드보다 더 간단한 소스로도 최대공약수가 구해진다는 것을 알고 '탈 서영기'를 외쳤다.

주어진 값들의 합을 구할 때도 '가우스'의 공식이 쓰이면 '계산 복잡도(Complexity)'가 O(n)에서 O(1)로 줄어든다. 최대공약수를 구하는 것도 유클리드 호제법을 이용하면 재귀 호출을 통해 문제를 풀 수 있다.

수학자로 유명한 유클리드(Euclid)는 최대공약수에 다음과 같은 성질이 있다는 것을 발견했다.

a와 b의 최대공약수는 'b'와 'a를 b로 나눈 나머지'의 최대공약수와 같다. 즉, gcd(a,b) = gcd(b, a % b)이다.

어떤 수와 0의 최대공약수는 자기 자신이다. 즉, gcd(n, 0) = n이다.

쉽게 말해 '어떤 수와 0의 최대공약수는 자기 자신'이라는 성질이다(이승찬, 2017).

gcd(60, 24)

    -> gcd(24, 12)

        -> gcd(12, 0)

            -> 12 (b가 0이므로 종료 조건)

        -> 12

    -> 12(최종 결과)

다음 섹션에서 컴퓨터 과학의 고전 문제라 불리는 '하노이 탑'을 통해 recursion을 한 번 더 연습해보자. 

참조

이승찬 저. (2017). 모두의 알고리즘 with 파이썬, 서울:(주)도서출판 길벗.