Algorithm | 피보나치 수

# 첫 시도: 재귀를 이용
def fibonacci(n):
    if n == 0:
        return 0
    if n == 1:
        return 1
    else:
        return fibonacci(n-1) + fibonacci(n-2)

위 코드의 경우 $n$이 크지 않은 경우 잘 작동하지만, $n$이 30을 넘어가면 시간이 매우 오래 걸린다. 이는 구조상 내부에서 함수를 매우매우매우 많이 반복해야하기 때문이다.

# 메모이제이션
def fibonacci(n):
    numbers = [0, 1]    # 처음 두 개의 피보나치 수
    for i in range(1, n):
        numbers.append(numbers[i] + numbers[i-1])
    return numbers[n]

위 코드의 경우 피보나치 수를 원소로 하는 리스트를 생성한 후 계속 append하여 $n$ 번째 수를 반환한다.