[재귀함수] 피보나치 수열

피보나치 수열이란?

세개의 항이 있을때, 첫번째 항과 두번째 항의 합이 세번째 항의 되는 수열.

 

첫번째 항과 두번째 항의 값은 모두 1이다.

세번째 항 = 첫번째 항 + 두번째 항 = 1 + 1 = 2

네번째 항 = 두번째 항 + 세번째 항 = 1 + 2 = 3

다섯번째 항 = 세번째 항 + 네번째 항 = 2 + 3 = 5

...

# n번째 피보나치 수열 구하기
def fib(n):
    if (n == 1) or (n ==2):
        return 1

    return fib(n-1)+fib(n-2)