백준 BaekJoon Online Judge // 10870

백준 알고리즘 BaekJoon Online Judge 10870번 "피보나치 수 5" 문제입니다.

def fibb(N):
  if N == 0:
    return 0
  elif N == 1:
    return 1
  else:
    return fibb(N-1) + fibb(N-2)

n = int(input())
print(fibb(n))

재귀 함수를 사용하여 피보나치 함수를 구현하는 문제다.

피보나치 수는 처음 두 개의 수는 0과 1로 시작하고 그 후의 수는 직전 2개의 수를 더한 값이다.

즉 0, 1, 1, 2, 3, 5, 8, 13... 으로 나열되는 수열을 피보나치 수열이라고 한다.

재귀 함수를 탈출구가 있어야 한다고 전 재귀 함수 포스트에서 말한바있다.

따라서 이번에도 탙출구인 N이 0 이나 1일 경우를 만들고 3번째 수부터는 직전 2개의 수를 더한 값이므로

fibb(N-1) + fibb(N-2)를 리턴해주면 피보나치 재귀 함수가 완성된다.