[Common Lisp code example] Euclid algorithm: GCD 찾기

두 수의 최대공약수(GCD)를 찾는 유클리드 알고리즘은 널리 알려져있다. 이 알고리즘을 리스프로 옮겨보자. 우선 코드를 보자.

(defun euclid (a b)
  (labels
      ((euclid-gcd (a b)
(if (zerop b)
    a
    (euclid-gcd b (mod a b)))))
  (let* ((gcd (euclid-gcd a b))
  (lcm (/ (* a b) gcd)))
      (values gcd lcm))))

이 코드는 최대공약수 뿐만 아니라 최소공배수까지 얻어내는 함수다. 실행 결과는 다음과 같다.

CL-USER> (euclid 462 1071)
21
23562

두 수를 받아야 하기 때문에 파라미터를 a, b로 둔다. labels는 함수 내에서 이용할 로컬 함수를 다시 정의할 수 있도록 해준다. euclid 함수 내에서 euclid-gcd를 다시 정의한 이유는 GCD를 우선적으로 얻어낸 후 이를 이용해 LCM값까지 출력해주기 위함이다.

euclid-gcd는 두 파라미터 a, b를 그대로 이용해서 recursive 호출을 이용해서 GCD를 얻어낸다. labels로 함수를 정의한 후에는 let* 함수가 나오는데, let*는 로컬 변수를 선언하는 역할을 한다. 위에서 정의한 euclid-gcd를 이용해서 얻는 GCD값을 gcd라는 변수에 넣고, 이 gcd를 이용해서 최소공약수를 얻은 후에 lcm 변수에 할당한다. 얻어낸 gcd값을 바로 아래 라인에서 lcm을 얻는데 사용하기 때문에 let* 함수를 사용한다. 그렇지 않은 경우엔 let을 사용하면 된다.

gcd와 lcm 변수에 각각 최대공약수와 최소공약수를 할당한 후에 이 값을 돌려줘야 되는데 리스프에서는 여러 개의 값을 돌려줄 수 있다. 그 방법이 가장 마지막 줄에 있는 values 함수를 이용하는 것이다.

실제 실행했을 때 21, 23562 두 수가 연속으로 리턴되는 것을 볼 수 있는데, values가 두 값을 넘겨주기 때문이다.