파이썬 재귀 함수로 n번째 피보나치 수 구하는 프로그램

문제 이해하기

하나의 숫자 n이 주어졌을 때, 재귀 함수(recursive function)를 정의하여 n번째 피보나치 항을 구하는 것이 이번 문제의 목표입니다.

예를 들어 입력값이 n = 8이라면 출력은 13이 됩니다. 피보나치 수열의 처음 몇 개 항은 다음과 같습니다.

0, 1, 1, 2, 3, 5, 8, 13, 21, 34...

해결 접근 방법

이 문제는 다음 단계에 따라 해결할 수 있습니다.

• solve() 함수를 정의하고, 이 함수가 숫자 n을 매개변수로 받도록 합니다.
• n <= 2인 경우에는 n - 1을 반환합니다. (첫 번째 항은 0, 두 번째 항은 1이기 때문입니다.)
• 그 외의 경우에는 solve(n - 1) + solve(n - 2)를 반환하여 앞의 두 항을 더한 값을 구합니다.

예제 코드

아래 구현 예시를 통해 더 쉽게 이해할 수 있습니다.

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

n = 8
print(solve(n))

입력

8

출력

13

동작 원리 살펴보기

n = 8이 입력되면 solve(8)은 solve(7)과 solve(6)을 호출하고, 각각의 함수는 다시 자신보다 작은 두 항을 호출하면서 재귀적으로 진행됩니다. 결국 n이 2 이하가 되면 기저 조건(base case)에 도달해 n - 1을 반환하고, 이 값들이 거슬러 올라가며 더해져 최종 결과인 13이 출력됩니다.

다만 이 재귀 방식은 동일한 하위 문제를 반복해서 계산하므로 시간 복잡도가 O(2ⁿ)으로 비효율적일 수 있습니다. 실무에서는 메모이제이션(memoization)이나 반복문 기반의 동적 계획법(DP)을 활용하면 O(n)의 시간 복잡도로 훨씬 빠르게 처리할 수 있습니다.