추석맞이 코딩 챌린지1- 피보나치 수

 

피보나치 수열은 수학에서 아래의 점화식으로 정의되는 수열이다.

피보나치 수는 0 번째 숫자인 0과 첫 번째 숫자인 1로 시작하며,

두 번째 숫자는 0 번째 수와 첫 번째 수의 합인 0 + 1 = 1,

세 번째 숫자는 첫 번째 수와 두 번째 수의 합인 1 + 1 = 2 의 값을 가진다.

​

숫자 n을 입력받아 피보나치 수열의 n번째 숫자를 출력하는 프로그램을 작성해보세요.

​

조건 1 : 입력받는 숫자 n은 2 이상의 자연수입니다.

조건 2 : n > 2인 피보나치 수에서, n번째 수 = (n - 2)번째 수 + (n - 1)번째 수 입니다.

조건 3 : 피보나치 수열을 나열하면 0, 1, 1, 2, 3, 5, 8, 13, 21, 34, ... 입니다.

정답

def fib(f):
    if (f == 0):
        return 0
    elif (f == 1 or f == 2):
        return 1
    else:
        return fib(f - 1) + fib(f - 2)
        
 a = int(input())
 result = fib(a)
 print(result)

재귀함수를 이용하다 보면 게속 스택이 증가를 하겠죠? 그러면 스택오버플로우가...

Anyway, 재귀함수도 다시 한번 공부를 해봐야겠네요! 치킨!