백준 10870번 피보나치 수 5 (파이썬)
재귀를 이용한 피보나치 수열 계산이다.
피보나치의 정의는 다음과 같다.
재귀를 사용하는 이유는 순환 호출을 사용했을 시 아래 사진과 같이 중복 호출이 많아져 비효율적이기 때문이다. 이러한 중복호출은 n이 커질수록 심해진다.
파이썬 코드는 다음과 같다.
#정수입력
n = int(input())
#피보나치 함수
def fibo(n):
if n == 0:
return 0
if n == 1:
return 1
if n >= 2:
return fibo(n-1)+fibo(n-2)
#피보나치 값 출력
print(fibo(n))