[JS] 피보나치 수 반환 / 재귀함수, 반복문, 시간복잡도,공간복잡도 비교

🚀 문제

재귀를 사용하여 n번째 피보나치 수를 반환하는 함수를 작성하시오.

      
      
      
    
function fibonacci(n) {
  // 여기에 코드 작성
}

console.log(fibonacci(10)); // 55

---

🔹 코드

      
      
      
    
function fibonacci(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(10)); // 55

---

📌 피보나치 수열 문제

🔎 1️⃣ 문제가 묻는 것

일반적으로 코딩 테스트에서 피보나치 수열을 반환하는 문제는 다음을 요구할 가능성이 큽니다:

✅ 정의:

• fibonacci(n) 함수는 n번째 피보나치 수를 반환해야 한다.
• 피보나치 수열은 다음과 같이 정의됨:
  • fibonacci(0) = 0
  • fibonacci(1) = 1
  • fibonacci(n) = fibonacci(n-1) + fibonacci(n-2), (n ≥ 2)

✅ 묻는 핵심 개념:

• 재귀(Recursive) 구현 가능 여부
• 반복문(Iterative)으로 구현 가능 여부
• 동적 계획법(DP) 적용 여부 → O(n)으로 최적화할 수 있는가?
• 시간 복잡도 & 공간 복잡도 고려
• 메모이제이션 적용 여부

---

🔎 2️⃣ 대중적인 피보나치 구현 방식

아래는 가장 많이 쓰이는 구현 방식입니다.

✅ (1) 재귀 (기본 구현, O(2ⁿ)) → 비효율적

      
      
      
    
function fibonacci(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

console.log(fibonacci(10)); // 55

• 시간 복잡도: O(2ⁿ) → 지수 시간 (느림)
• 공간 복잡도: O(n) → 재귀 호출로 인해 스택 프레임이 n개 쌓임
• 단점: 불필요한 중복 연산이 많아 n이 크면 매우 느려짐

✅ (2) 반복문 (O(n), 효율적)

      
      
      
    
function fibonacci(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
    
    let a = 0, b = 1, temp;
    for (let i = 2; i <= n; i++) {
        temp = a + b;
        a = b;
        b = temp;
    }
    return b;
}

console.log(fibonacci(10)); // 55

• 시간 복잡도: O(n)
• 공간 복잡도: O(1) (추가 배열 없이 변수만 사용)
• 장점: 반복문을 사용해 불필요한 계산을 줄임 → 실전에서 가장 추천되는 방식

✅ (3) 메모이제이션 (Top-down, O(n))

      
      
      
    
function fibonacci(n, memo = {}) {
    if (n in memo) return memo[n];
    if (n === 0) return 0;
    if (n === 1) return 1;
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    return memo[n];
}

console.log(fibonacci(10)); // 55

• 시간 복잡도: O(n)
• 공간 복잡도: O(n) (재귀 호출 스택 + 저장 공간)
• 장점: 재귀이지만 중복 계산을 제거하여 성능 개선

✅ (4) 동적 계획법 (Bottom-up, O(n))

      
      
      
    
function fibonacci(n) {
    let dp = [0, 1];
    for (let i = 2; i <= n; i++) {
        dp[i] = dp[i - 1] + dp[i - 2];
    }
    return dp[n];
}

console.log(fibonacci(10)); // 55

• 시간 복잡도: O(n)
• 공간 복잡도: O(n) (배열 사용)
• 장점: 반복문 기반으로 효율적

---

🔥 하지만, 재귀는 비효율적!

• 기본적인 재귀 구현은 O(2ⁿ)의 지수 시간 복잡도를 가지므로 매우 비효율적.
• 예를 들어, fibonacci(50)을 호출하면, fibonacci(49), fibonacci(48), ..., fibonacci(1)을 여러 번 중복 계산해야 함.

✅ 실전에서는 이렇게 최적화해야 함:

1. 메모이제이션 (Memoization, Top-Down DP)
2. 반복문 (Iterative, O(n), O(1))

---

🛠 재귀를 요구하면 어떻게 접근해야 할까?

1️⃣ 먼저 순수 재귀로 구현한다.

      
      
      
    
function fibonacci(n) {
    if (n === 0) return 0;
    if (n === 1) return 1;
    return fibonacci(n - 1) + fibonacci(n - 2);
}

 

2️⃣ 면접관이 최적화를 요구하면 메모이제이션을 추가한다.

 

      
      
      
    
function fibonacci(n, memo = {}) {
    if (n in memo) return memo[n];
    if (n === 0) return 0;
    if (n === 1) return 1;
    memo[n] = fibonacci(n - 1, memo) + fibonacci(n - 2, memo);
    return memo[n];
}

 

3️⃣ 시간 복잡도를 최적화해야 한다면 반복문을 사용한다.

      
      
      
    
function fibonacci(n) {
    let a = 0, b = 1;
    for (let i = 2; i <= n; i++) {
        [a, b] = [b, a + b];
    }
    return b;
}

 

---

🔑 결론

• 실무에서는 O(n) 반복문 방식이 더 효율적이므로, 면접에서 "이 방식은 비효율적이니 최적화가 필요하다"는 점을 설명할 수 있으면 좋음.
• 면접이나 코딩 테스트에서는 재귀 → 메모이제이션 → 반복문 최적화 순서로 접근하면 좋음. 🚀

 

📖 5️⃣ 공부할 자료

1️⃣ 피보나치 수열 - 위키백과
2️⃣ Big-O 시간 복잡도 개념
3️⃣ 동적 계획법 (DP) 개념
4️⃣ 메모이제이션 vs 반복문 비교