재귀(recursion)는 함수가 자기 자신을 반복적으로 호출하며 문제를 해결하는 강력한 프로그래밍 기법입니다. 이번 글에서는 파이썬에서 재귀 방식을 활용해 피보나치 수열을 구하는 방법을 코드 예제와 함께 자세히 살펴보겠습니다.
피보나치 수열과 재귀의 개념
피보나치 수열은 첫 번째와 두 번째 항이 각각 0과 1이며, 세 번째 항부터는 바로 앞의 두 항을 더한 값으로 이루어지는 수열입니다. 즉, 0, 1, 1, 2, 3, 5, 8, 13처럼 이어지는 패턴을 가집니다.
재귀 방식으로 피보나치 수열을 구하려면 fibonacci_recursion이라는 이름의 메서드를 정의하고, 입력값을 매개변수로 전달합니다. 이 메서드는 입력값의 크기를 점점 줄여가면서 스스로를 다시 호출하는 방식으로 동작합니다.
예제 코드
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
print("항의 개수는 다음과 같습니다:")
print(num_terms)
if num_terms <= 0:
print("양의 정수를 입력해 주세요...")
else:
print("피보나치 수열은 다음과 같습니다:")
for i in range(num_terms):
print(fibonacci_recursion(i))
실행 결과
항의 개수는 다음과 같습니다: 12 피보나치 수열은 다음과 같습니다: 0 1 1 2 3 5 8 13 21 34 55 89
코드 동작 원리 상세 설명
재귀 함수 정의: fibonacci_recursion이라는 메서드를 정의하고, 값을 매개변수로 전달받습니다.
기저 조건(base case) 설정: 입력값이 1 이하일 경우 그대로 반환하도록 하여 재귀 호출이 무한히 반복되는 것을 방지합니다.
재귀 호출: 입력값에서 1을 뺀 값과 2를 뺀 값에 대해 각각 함수를 다시 호출한 뒤, 두 결과를 더하여 반환합니다. 이 과정은 결과가 도출될 때까지 반복됩니다.
항의 개수 지정: 함수 외부에서 구하고자 하는 항의 개수(num_terms)를 정의하고 콘솔에 출력합니다.
유효성 검사: 입력값이 0 이하인 경우 양의 정수를 입력하도록 안내 메시지를 출력합니다.
반복문으로 수열 출력: 범위 내 숫자들을 하나씩 순회하면서 재귀 메서드를 호출하고, 그 결과를 콘솔에 차례대로 출력합니다.
참고 사항: 성능 최적화
재귀 방식은 코드가 직관적이라는 장점이 있지만, 같은 값을 여러 번 중복 계산하기 때문에 항의 개수가 많아지면 실행 속도가 급격히 느려질 수 있습니다. 실무에서는 메모이제이션(memoization) 기법을 함께 사용하거나 functools 모듈의 lru_cache 데코레이터를 적용하면 중복 연산을 줄여 성능을 크게 개선할 수 있습니다.