[파이썬] 10870번: 피보나치 수 5

10870번: 피보나치 수 5 (acmicpc.net)

10870번: 피보나치 수 5

재귀함수를 이용하여 피보나치 수를 만들어야 한다.

피보나치 수열
0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, 89, 144, 233, 377, 610, 987, 1597 ...

 

n을 입력받은 후 n번째 피보나치 수를 출력해야 한다.

ex) n = 5, 출력값은 3

 

n = int(input())

def fibonacci(n):
    if n <= 1:
        return n
    return fibonacci(n - 1) + fibonacci(n - 2)

print(fibonacci(n))

피보나치 수열의 성질을 활용한다.

Fn = Fn-1 + Fn-2 

 

if문

F0 = 0, F1 = 1이므로 n이 1과 같거나 작을 경우에는 n을 그대로 출력한다.

 

return

fibonacci 함수를 다시 호출하여 fibonacci(n - 1) + fibonacci(n - 2)를 수행한 결과값을 리턴한다.