[Python] 피보나치 수열 구현 (fibonacci sequence)

이번에는 저번 sorted 포스팅에 이어 과제로 자주 나오는

피보나치 수열을 구현해보겠다.

 

우선 피보나치 수열이란

첫째 항, 둘째 항이 모두 1이면 그 뒤의 모든 항은 그 앞 두 항의 합인 수열이다.

 

우선 피보나치 수열을 살펴보자

 

$$ \begin{align} &F_{0}=&0\\ &F_{1}=&1\\ &F_{n}=&F_{n-2}&+&F_{n-1}& \end{align} $$

 

위와 같은 일반항으로 수열이 나타난다.

 

결국 0, 1, 1, 2, 3, 5, 8, 13, 21 ...... 이런식으로 증가하는 수열이다.

 

그렇다면 구현해보겠다

 

우선 우리가 기존에 알던 방식으로 해보겠다.

 

$F_{1}$항부터 시작하도록 하겠다.

 

def fibonacci(number):
    i=2
    arr=[1,1]
    if(number<=2):
        return arr[:number]
        
    while i<number:
        arr.append(arr[-2]+arr[-1])
        i+=1
        
    return arr

 

첫 항과 두 번째 항은 고정해주고 3 번째 항부터 전전 항과 전 항을 합해서 계산 하도록 한다.

 

그렇다면 다음으로 일반적으로 피보나치를 구현할 때 쓰는 재귀함수 방식으로 구현해 보겠다.

 

def fibonacci(number):
    i=2
    arr=[1,1]
    if(number<=2):
      return arr[:number]

    prev = fibonacci(number-1)
    return prev + [prev[-2]+prev[-1]]

 

재귀함수를 이해할 때 예제로 가장 많이 나오는 함수가 피보나치이다.

 

이 부분들을 직접 number가 1,2,3일 때 대입 해보며 생각 해본다면 이해가 될 것이다.

 

생각을 많이 하지 않았고 파이썬에 익숙하지 않기에 좀 더 파이써닉한 좋은 방법이 있을 거라고 생각한다.

 

그렇다면 테스트를 해보겠다.

 

assert list(fibonacci(10)) == [1, 1, 2, 3, 5, 8, 13, 21, 34, 55]
assert sum(fibonacci(5)) == 12

 

잘 구현된 것을 확인할 수 있다.