2025-09-03 01:36
Tags: 프로그래밍 기초
재귀
- 큰 문제를 동일한 구조의 더 작은 문제로 나누어 해결하는 프로그래밍 기법
- 무한 반복을 막는 ‘탈출 조건(Base Case)‘과 자기 자신을 다시 호출하는 ‘재귀 호출(Recursive Step)‘로 구성
- 코드를 간결하게 만들지만, 메모리 사용량이 많아 스택 오버플로우를 유발할 수 있으므로 신중하게 사용
# 팩토리얼을 계산하는 재귀 함수
def factorial(n):
# 1. 탈출 조건 (Base Case)
# n이 1일 때, 더 이상 쪼갤 수 없으므로 1을 반환하고 멈춘다.
if n == 1:
return 1
# 2. 재귀 호출 (Recursive Step)
# n과 (n-1)의 팩토리얼 결과를 곱한다.
else:
return n * factorial(n - 1)
# 함수 호출
print(f"5! = {factorial(5)}") # 출력: 5! = 120| 특징 | 재귀 (Recursion) | 반복문 (Iteration) |
|---|---|---|
| 코드 가독성 | 문제의 구조를 직관적으로 표현하여 코드가 간결하고 이해하기 쉬운 경우가 많다. (예: 트리 순회) | 코드가 길어지고 복잡해질 수 있지만, 로직의 흐름이 명시적으로 드러난다. |
| 성능 | 함수 호출에 따른 오버헤드가 발생하여 일반적으로 반복문보다 느리다. | 추가적인 함수 호출이 없어 성능 면에서 더 효율적이다. |
| 메모리 사용량 | 호출될 때마다 호출 스택에 메모리가 쌓여, 깊이가 깊어지면 스택 오버플로우가 발생할 수 있다. | 정해진 변수만 사용하여 메모리 사용량이 일정하고 예측 가능하다. |
| 적합한 문제 유형 | 분할 정복(Divide and Conquer), 트리/그래프 탐색, 백트래킹 등 문제의 구조가 재귀적인 경우 | 선형적인 데이터 구조를 순회하거나, 정해진 횟수만큼 동일한 작업을 반복하는 경우 |