재귀 함수로 피보나치 수열 구현하기

피보나치 수열은 각 숫자가 이전 두 숫자의 합으로 이루어진 수열입니다.

처음 두 숫자는 보통 0과 1로 시작되며, 0, 1, 1, 2, 3, 5, 8, 13, 21, ... 와 같이 진행됩니다.

피보나치 수를 수학적으로 표현하면 F(n) = F(n-1) + F(n-2)로 정의할 수 있으며, 이를 파이썬 코드로 구현하면 다음과 같습니다.

피보나치 수열 구현

def fibonacci(n):
    if n <= 1:
        return n
    else:
        return fibonacci(n-1) + fibonacci(n-2)

시간 복잡도

재귀 함수로 구현한 피보나치 수열의 시간 복잡도는 O(2^n)입니다. 이는 함수가 각 단계에서 두 개의 함수 호출을 하며, 이 호출들이 지수적으로 증가하기 때문입니다.