함수 코드가 짧고 잘 작성된 것처럼 보인다. 하지만 이 함수의 작동 과정을 파악하기 위해서는 함수의 실행 원리와 수학 문장을 알고리즘으로 변환한 과정을 잘 이해하고 있어야 한다.

0보다 큰 두 정수 a, b를 동시에 나누는 최대 양수 c를 최대공약수(GCD, Greatest Common Divisor)라고 정의한다. 수식으로 표현하면 다음과 같다.

gcd(a, b) = max{ c∈N | c|a and c|b }

여기에 a < b라는 가정을 추가하면 다음 두 재귀식(recursive formula)이 성립하는 것을 쉽게 알 수 있다.

gcd(a, b) = gcd(a, b – a)

(7.1)

gcd(a, b) = gcd(a, b%a)

(7.2)

다시 말해 둘 중 작은 수를 빼거나 큰 수를 작은 수로 모듈로 연산을 해도 gcd는 그대로다. 이 식은 고대 그리스 시절부터 사용하던 것으로서 유클리드(Euclid)(약 300 B.C.)가 발견했다고 알려졌지만 그보다 먼저 나왔을 수도 있다.

앞에 나온 gcd2 함수는 식 7.2를 이용한다. 먼저 9줄에서 이 함수의 선행 조건을 만족하는지 검사한다. 즉, 첫 번째 인수가 두 번째 인수보다 작거나 같은지 확인한다. 이 작업은 assert.h 헤더 파일에서 제공하는 assert 매크로로 처리한다. 이 함수를 호출할 때 지정한 인수가 조건을 만족하지 못하면 메시지를 출력하면서 프로그램이 멈춘다(assert는 8.7절에서 자세히 설명한다).