모두의 알고리즘 문제 05. 최대공약수 구하기 연습문제

# 연습문제 5-1 n번째 피보나치 수를 구하는 알고리즘을 재귀호출을 이용해서 구현해 보시오.

def fibo (n):
    if n==0:
        return 0
    if n==1:
        return 1
    return fibo(n-1) + fibo(n-2)

print(fibo(7)) #결과 13
print(fibo(10)) #결과 55

#재귀호출 문제는 자신없어서 암담했는데 일단 배운대로 종료조건 설정하고 고민해보다가
#문제 힌트의 (7번값 = 5번값 + 6번값) 을 보고 대강 감을 잡고 풀었다.

#이번 재귀호출은 그림으로 표현하자면 트리 구조처럼 된다.
#fibo(5)를 호출하면 (4)와 (3)이 호출되고, (4)는 (3)과 (2)를 호출하고, (3)은 (2)와 (1)을 호출한다.
#이렇게 하나의 함수가 두개의 함수를 호출하는 식으로 트리 구조가 완성되고 아래에서부터 값을 반환받아가며 최상위 루트까지 올라간다.