1.2피보나치 수

재귀 함수에 익숙해지도록 한 가지 예제를 더 만들어 봅시다.

피보나치(fibonacci) 수는 0과 1부터 시작하여 다음 수가 앞의 두 수를 더한 값이 되는 수열입니다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34, 55, …

재귀 함수를 만들 단서는 ‘다음 수가 앞의 두 수를 더한 값’이라는 문장에서 얻을 수 있습니다. 두 번째로 필요한 것은 ‘탈출 조건’입니다. 정의를 보면 맨 처음 수가 0과 1입니다. 이 부분을 탈출 조건으로 쓰겠습니다. 코드로 만들어 볼까요?

코드 13-3 data_structure_2/ds_1/fibonacci.py ①

def fibonacci(n):    #1
    if n = = 1:      #2
        return 0
    elif n = = 2:    #3
        return 1

    return fibonacci(n-2) + fibonacci(n-1)  #4