유클리드 알고리즘
'유클리드 알고리즘'은 주어진 두 수 사이에 존재하는 최대공약수를 구하는 알고리즘입니다.
과정은 다음과 같습니다.
- m을 n으로 나눕니다.
- 나머지 r리 0이면 n이 최대공약수입니다. 나머지가 0이 아니라면 m의 값을 n으로 설정하고, n의 값은 r로 설정한 다음 1로 되돌아가서 반복합니다.
저자의 표현을 따르면 '군더더기 하나 없는 아름다운 시와 같은 알고리즘'입니다.
코드로 표현하면 이렇습니다. 삼항연산자를 사용했습니다.
const gcd = (m, n) => m % n === 0 ? n : gcd(n, m % n);두 숫자 582와 129를 예로 들어보겠습니다.
[ 1단계 ] 582 = 129 x 4 + 66 -> 582를 129로 나누면 몫이 4이고, 나머지가 66입니다.
[ 2단계 ] 129 = 66 x 1 + 63 -> 129를 66으로 나누면 몫이 1이고, 나머지가 63입니다.
[ 3단계 ] 66 = 63 x 1 + 3 -> 66을 63으로 나누면 몫이 1이고 나머지가 3입니다.
[ 4단계 ] 63 = 3 x 21 + 0 -> 나머지가 0이므로 두 수의 최대 공약수는 3입니다.
각 단계의 표현이 'm = n * C + r'의 형태로 되어 있고, 다음 단게로 넘어갈 때마다 n이 m의 자리로 이동하고, r은 n의 자리로 이동하고 있습니다.
유클리드가 개발한 이 알고리즘은 오늘에 이르기까지 최대공약수를 구하는 방법 중에서는 가장 효율적인 방법의 하나로 통용되고 있습니다.
꼬리재귀
재귀적 함수를 원래 함수의 꼬리 부분에서 호출하는 경우를 일컬어 '꼬리 재귀'라고 부릅니다.
재귀 알고리즘은 함수를 호출하는 위치의 주소값이 스택에 저장됩니다. 그 이유는 원래 위치로 되돌아가서 남은 일을 마저 끝내야 하기 때문입니다. 그렇다면 만약 원래 위치로 돌아갔을 때 할 일이 남아 있지 않은 경우는 어떨까요?
물론 이런 경우에는 호출된 함수가 리턴되고 나서 굳이 원래 위치로 돌아갈 필요가 없습니다. 이 경우에는 '호출된' 함수가 리턴될 때 '호출한' 함수도 동시에 리턴될 수 있기 때문입니다.
위의 gcd 함수는 꼬리재귀하고 할 수 있습니다. 경우에 따라 n을 리턴하거나 재귀 함수를 리턴하기 때문입니다.
