BOJ 10870번 : 피보나치 수 5

안녕하세요. 지난 포스팅의 BOJ 10872번 : 팩토리얼에서는 컴퓨터공학에서의 재귀함수를 수학적인 점화식으로 표현하는 방법에 대해서 알아보았습니다. 따라서, 재귀함수와 관련된 문제는 점화식을 잘 세우는 것이 중요하다는 것을 알게 되었죠. 오늘도 재귀함수와 관련된 유명한 문제를 풀어보도록 하겠습니다. 

 

 

완벽한 코딩은 존재하지 않습니다. 제가 제출한 코드 역시 마찬가지고 그저 참고만 해주시길 바랍니다. 

 

핵심 포인트

• 재귀함수의 정의
• 피보나치 수열의 정의

 

제출 코드

def fibonacci(n) :
    if n == 0 : return 0
    elif n == 1 or n == 2 : return 1
    else : return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(int(input())))

 

해설

이 문제도 재귀함수를 이용해서 문제를 해결할 수 있습니다. 일단, 재귀함수의 기본인 점화식은 이미 문제에서 제공해주고 있습니다. $n /ge 2$에 대해서 $F_{n} = F_{n - 1} + F_{n - 2}$입니다. 이때, $F_{0} = 0$이고, $F_{1} = F_{2} = 1$로 이는 재귀함수의 종료조건이 됩니다. 따라서, 위의 코드와 마찬가지로 $n  = 0$일 때는 0을 반환하고 $n = 1$ 또는 $n = 2$일 때는 1을 반환해서 종료조건을 명시해주면 됩니다. $n \ge 2$에 대해서는 점화식 그대로 fibonacci(n - 1) + fibonacci(n - 2)를 반환해주면 종료조건을 맞이할 때 까지 계속 함수를 호출하게 되겠죠. 

 

참고자료 및 그림출처

백준 코딩 문제