JavaScript로 구현하는 피보나치 수열 (Fibonacci Sequence)

피보나치 수열이란?

"피보나치 수열"은 수학과 컴퓨터 과학에서 매우 널리 알려진 수열 중 하나입니다. 이 수열은 첫 번째 항이 0, 두 번째 항이 1로 시작하며, 이후의 항은 바로 앞의 두 항을 더한 값으로 정의됩니다. 즉, 세 번째 항부터는 F(n) = F(n - 1) + F(n - 2)의 관계를 가집니다.

예를 들어 앞의 몇 항을 나열하면 다음과 같습니다:

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610...

이러한 규칙은 단순하면서도 수학적으로 아름다운 구조를 가지며, 황금비와도 연관되어 있는 특성이 있습니다. 또한, 프로그래밍 언어나 알고리즘 교육에서 "재귀 호출", "반복문", "동적 계획법" 등의 개념을 소개할 때 자주 사용되는 대표 예제이기도 합니다.

피보나치 수열은 문제 해결 방식에 따라 시간과 공간 복잡도가 크게 달라지기 때문에, 다양한 구현을 비교하면서 학습하면 큰 도움이 됩니다.

---

자바스크립트로 구현하는 피보나치 수열

1. "재귀 호출" 방식

재귀(recursion)는 함수가 자기 자신을 호출하는 방식으로 문제를 해결하는 기법입니다. 피보나치 수열은 수식 자체가 재귀적 정의이기 때문에 구현도 매우 직관적입니다.

// 피보나치 수를 재귀적으로 계산하는 함수
function fibonacciRecursive(n) {
  if (n <= 1) return n; // 종료 조건: 0 또는 1이면 자기 자신 반환
  return fibonacciRecursive(n - 1) + fibonacciRecursive(n - 2); // 재귀 호출
}

console.log(fibonacciRecursive(6)); // 결과: 8

이 방식은 이해하기 쉽고 코드도 간단하지만, 동일한 계산을 반복적으로 수행하게 되어 비효율적입니다. 특히 n이 클수록 처리 시간이 기하급수적으로 증가합니다.

"시간 복잡도": O(2^n)
"공간 복잡도": O(n) (호출 스택 기준)

재귀 방식은 주로 "재귀 호출 구조"를 이해하거나, 아주 작은 n 값에 대해 간단한 구현을 할 때 사용됩니다.

---

2. "반복문" 방식

재귀의 성능 문제를 해결하기 위한 가장 간단한 방법은 반복문을 이용한 구현입니다. 메모리를 최소화하면서 빠른 속도로 결과를 도출할 수 있는 장점이 있습니다.

// 반복문을 이용한 피보나치 수열 계산
function fibonacciLoop(n) {
  if (n <= 1) return n; // 기본 조건
  let prev = 0, curr = 1;
  for (let i = 2; i <= n; i++) {
    const next = prev + curr; // 다음 피보나치 수 계산
    prev = curr;              // 이전 값 업데이트
    curr = next;              // 현재 값 업데이트
  }
  return curr;
}

console.log(fibonacciLoop(6)); // 결과: 8

이 방식은 처리 속도가 빠르며, 반복적인 계산을 방지합니다. 또한 "공간 복잡도"가 O(1)로 매우 효율적입니다.

"시간 복잡도": O(n)
"공간 복잡도": O(1)

반복문 방식은 n 값이 커질 때에도 안정적으로 작동하며, 실제 프로덕션 코드에서도 자주 사용되는 방법입니다.

---

3. "동적 계획법" (Memoization)

재귀 방식의 단순한 구조와 반복문의 효율성을 결합한 방식이 바로 동적 계획법입니다. 이미 계산한 결과를 저장해두고, 이후 필요 시 다시 계산하지 않고 활용함으로써 성능을 높이는 기법입니다.

// 메모이제이션을 이용한 피보나치 수열 계산
function fibonacciMemo(n, memo = {}) {
  if (n <= 1) return n; // 기본 조건
  if (memo[n]) return memo[n]; // 이미 계산된 값이 있다면 반환

  // 계산 후 저장
  memo[n] = fibonacciMemo(n - 1, memo) + fibonacciMemo(n - 2, memo);
  return memo[n];
}

console.log(fibonacciMemo(6)); // 결과: 8

메모이제이션(memoization)을 통해 이전 계산 결과를 저장해두기 때문에 불필요한 중복 계산을 방지할 수 있습니다. 이는 특히 n이 매우 클 때 큰 성능 차이를 만듭니다.

"시간 복잡도": O(n)
"공간 복잡도": O(n)

---

방식별 비교 요약

방식	시간 복잡도	공간 복잡도	특징
재귀 호출	O(2^n)	O(n)	구현은 간단하지만 매우 비효율적
반복문	O(n)	O(1)	빠르고 메모리 효율이 좋으며 실무에서도 자주 사용됨
동적 계획법	O(n)	O(n)	재귀 + 캐싱으로 성능과 코드 구조 모두 고려 가능

각 방식은 상황에 따라 적절히 선택하는 것이 중요합니다. 예를 들어 성능이 중요한 실무 환경에서는 반복문 방식이 적합하고, 코드의 명확성이 우선되는 교육적 목적에서는 재귀 호출이나 동적 계획법이 유용할 수 있습니다.

---

출력 예시

다음 코드는 0부터 10까지의 피보나치 수열을 반복문 방식으로 출력합니다.

for (let i = 0; i <= 10; i++) {
  console.log(fibonacciLoop(i));
}

// 출력 결과:
// 0
// 1
// 1
// 2
// 3
// 5
// 8
// 13
// 21
// 34
// 55

이러한 반복문 출력은 프로그램 실행 흐름을 눈으로 확인하기에 매우 적합하며, 사용자와의 인터랙션이 필요한 웹페이지에서도 활용됩니다.

---

마무리 및 추천 자료

"피보나치 수열"은 단순한 구조지만 다양한 프로그래밍 기법을 통해 효율성과 성능을 극대화할 수 있는 대표적인 예제입니다. 특히 자바스크립트에서는 동기/비동기 환경에서의 알고리즘 학습이나 인터랙티브 UI 구현에도 활용 가능성이 높습니다.

한 문제를 재귀, 반복문, 동적 계획법 등 다양한 방법으로 접근하며 사고의 유연성을 기를 수 있고, 이는 코딩 테스트나 기술 면접에서도 유용하게 쓰일 수 있습니다.

피보나치 수열은 또한 컴퓨터 공학 전반에서 중요한 수학적 기초 개념이기도 하며, 정렬, 탐색, 분할 정복 알고리즘 등 다양한 분야와도 연계될 수 있습니다.

추가로 학습을 원하시는 분들을 위해 다음의 자료를 추천합니다:

• MDN - 함수 기본 개념
• Visualgo - Algorithm 시각화 도구
• replit - JavaScript 실습 환경
• freeCodeCamp