재귀(Recursion)를 활용해 피보나치 수열을 출력하는 Python 프로그램

재귀(Recursion) 방식으로 피보나치 수열을 출력해야 하는 경우, 기저 조건(base case)에 도달할 때까지 자기 자신을 반복해서 호출하는 메서드를 선언하면 됩니다. 재귀는 하나의 큰 문제를 동일한 구조를 가진 더 작은 하위 문제로 나누어 해결하는 프로그래밍 기법으로, 각 항이 이전 두 항의 합으로 정의되는 피보나치 수열을 구현하기에 특히 적합합니다.

아래에서 실제 구현 예제를 확인해 보겠습니다.

예제 코드

def fibonacci_recursion(my_val):
    if my_val <= 1:
        return my_val
    else:
        return(fibonacci_recursion(my_val-1) + fibonacci_recursion(my_val-2))

num_terms = 12

if num_terms <= 0:
    print("Enter a positive integer")
else:
    print("The fibonacci sequence is :")
    for i in range(num_terms):
        print(fibonacci_recursion(i))

실행 결과

The fibonacci sequence is :
0
1
1
2
3
5
8
13
21
34
55
89

코드 설명

• 'fibonacci_recursion'이라는 이름의 함수를 정의하고, 하나의 값을 매개변수로 전달받습니다.

• 전달받은 값이 1 이하이면 해당 값을 그대로 반환합니다. 이것이 재귀 호출을 멈추는 역할을 하는 기저 조건(base case)입니다.

• 값이 1보다 크면 자기 자신을 다시 호출하여 (n-1)번째 항과 (n-2)번째 항의 합을 계산하고, 기저 조건에 도달할 때까지 이 과정을 반복합니다.

• 변수 'num_terms'에 출력할 피보나치 수열의 항 개수를 정의합니다.

• 항 개수가 0 이하이면 양의 정수를 입력하라는 안내 메시지를 출력하고, 그렇지 않으면 반복문을 통해 각 항을 순서대로 계산하여 콘솔에 표시합니다.

성능 개선 팁

위와 같은 단순 재귀 구현은 같은 값을 여러 번 중복 계산하게 되어 시간 복잡도가 지수급(O(2ⁿ))으로 증가합니다. Python의 functools.lru_cache 데코레이터를 함수 위에 추가하면 이미 계산된 결과가 캐싱되어 실행 속도를 크게 향상시킬 수 있습니다.