[백준 10870번] 피보나치 수 5

난이도 : 브론즈 Ⅱ
사용언어 : 파이썬
단계별로 풀어보기 > 재귀

https://www.acmicpc.net/problem/10870

10870번: 피보나치 수 5

 

• 최초 풀이 

def fibo(n) :
    lst = [0,1]
    if n == 0 : return lst[0]
    if n == 1: return lst[1] 
    while n >= 2 : 
        a = (lst[-1]+lst[-2])
        lst.append(a)
        n = n-1
    return lst[-1]

n = int(input())
print(fibo(n))

아이디어 

 

[0,1,1,2,3,5,···] 리스트를 직접 만들고, 그 리스트의 n인덱스 값이 출력되도록 했다.

리스트를 만든 방법은 n이 2보다 크거나 같을 경우, 리스트의 마지막 두 수를 더한 값을 추가하도록 했다. (while 반복)

 

• 재귀호출함수 개념 이해 후 풀이

def fibo(n) : 
    if n == 0 : return 0
    elif n == 1 : return 1
    else : return fibo(n-1) + fibo(n-2) 
    
n = int(input())
print(fibo(n))

아이디어 

 

함수 안에서 함수 자기자신을 호출하는 방식을 재귀호출함수라고 한다.

해당 함수가 계속 반복되지 않으려면 함수 내 종료조건을 필수로 잡아줘야한다! 

현재 fibo 함수의 경우, n의 값이 0 또는 1일 경우 해당 값을 반환하면서 함수가 종료된다.

 

재귀호출함수 작동을 이해하려고 정리

 

 

재귀함수를 잘 이용하면, 프로그래밍에 유용할 것 같다