[백준 알고리즘] 10870번 python 피보나치 재귀문제

 

재귀문제에 대표적인 피보나치문제이다

Fn = Fn-1 + Fn-2 (n ≥ 2) 가 핵심이며 3번째수는 전 1번째 수와 2번째 수를 더하고 n은 2이상 존재해야하므로 1또는 0이되면 마지막 노드이며 재귀적으로 전체를 더해주면 피보나치 수열이된다.

 

아래의 코드를 해석해보면 N이 4일때

                        

 

 

import sys

def bonacci(N):
    if(N==1):
        return 1
    elif(N==0):
        return 0



    return bonacci(N-1) + bonacci(N-2)


if __name__ == "__main__":
    N = int(sys.stdin.readline().rstrip())

    print(bonacci(N))