재귀 알고리즘 - 피보나치 수열 이해와 효율적인 구현 방법

피보나치 수열 개요

• 피보나치 수열은 0과 1로 시작하며 각 항이 바로 앞의 두 항의 합으로 이루어지는 수열입니다.
• 0, 1, 1, 2, 3, 5, 8, 13과 같은 형태를 가지고 있습니다.

피보나치 수열 재귀 동작원리

• n이 1이하가 될 경우 n을 출력합니다.
• 그렇지 않을 경우에는 n - 1과 n - 2을 재귀적으로 호출하여 더해줍니다.

피보나치 수열 재귀 코드 예시

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

 

피보나치 수열 재귀 시간 복잡도

                  fib(5)
                /        \
            fib(4)        fib(3)
            /    \        /    \
        fib(3)  fib(2)  fib(2) fib(1)
        /    \    /    \
    fib(2) fib(1)fib(1) fib(0)
    /    \
fib(1) fib(0)

많은 중복 계산이 발생되며 시간 복잡도는 지수적으로 증가하게 됩니다. O(2^n)

그래서 피보나치 수열을 풀때는 다양한 방법이 있습니다.

반복적 계산, 메모이제이션, 피사노 주기, 행렬등이 있습니다.

피보나치 수열 반복 코드 예시

function fibonacci(n) {
 let prev = 0
 let current = 1
 for(let i = 2; i <= n; i++) {
  const next = prev + current
  prev = current
  current = next
 }
 return current
}

 

피보나치 수열 반복 시간 복잡도

• n까지 반복하면서 더하는거기 때문에 O(n)이 됩니다.