루카스 수열이란?
루카스 수열(Lucas Numbers)은 프랑스 수학자 에두아르 루카스(Édouard Lucas)의 이름을 딴 수열로, 피보나치 수열과 매우 유사한 점화식으로 정의됩니다. 다만 초기값이 다르다는 점이 특징입니다.
L(0) = 2
L(1) = 1
L(n) = L(n-1) + L(n-2)
이 정의에 따르면 루카스 수열은 2, 1, 3, 4, 7, 11, 18, 29, 47, 76...과 같은 형태로 이어집니다.
문제 정의
숫자 n을 입력받아 n번째 루카스 수를 반환하는 자바스크립트 함수를 작성해야 합니다.
재귀 함수로 구현하기
가장 직관적인 방법은 점화식을 그대로 재귀 함수로 옮기는 것입니다. 기저 조건(base case)인 n이 0일 때는 2를, n이 1일 때는 1을 반환하고, 그 외의 경우에는 앞의 두 항을 더한 값을 재귀적으로 구합니다.
const num = 21;
const lucas = (num = 1) => {
if (num === 0)
return 2;
if (num === 1)
return 1;
return lucas(num - 1) + lucas(num - 2);
};
console.log(lucas(num));
실행 결과
위 코드를 실행하면 콘솔에 다음과 같은 결과가 출력됩니다.
24476
즉, 21번째 루카스 수는 24476입니다.
성능 개선: 메모이제이션(Memoization)
단순 재귀 방식은 같은 값을 여러 번 중복 계산하기 때문에 n이 커지면 시간 복잡도가 지수적으로 증가합니다(시간 복잡도 O(2ⁿ)). 이를 개선하려면 이미 계산한 값을 캐시에 저장하는 메모이제이션 기법을 활용할 수 있습니다.
const lucasMemo = (() => {
const cache = { 0: 2, 1: 1 };
const fn = (num) => {
if (cache[num] !== undefined)
return cache[num];
cache[num] = fn(num - 1) + fn(num - 2);
return cache[num];
};
return fn;
})();
console.log(lucasMemo(21)); // 24476메모이제이션을 적용하면 각 항을 한 번씩만 계산하므로 시간 복잡도가 O(n)으로 크게 향상되어, 큰 n 값에서도 빠르게 결과를 얻을 수 있습니다.