computer science
재귀: 자기 자신을 호출하는 함수를 통한 문제 해결 기법
재귀(Recursion)는 함수가 자기 자신을 호출하여 문제를 해결하는 프로그래밍 기법이다. 복잡한 문제를 더 작은 부분 문제로 나누어 해결하고, 그 결과를 합쳐 전체 문제를 해결한다. 반복문과 유사하지만, 코드의 가독성을 높이고 특정 문제에 대한 우아한 해법을 제시할 수 있다.
송민성3분 읽기
1. 개념
재귀(Recursion)는 함수가 자기 자신을 호출하는 것이다. 모든 재귀 함수에는 반드시 종료 조건이 있어야 하고 없으면 무한 루프에 빠진다. 문제를 더 작은 부분 문제로 나눈 뒤 각 부분 문제를 같은 방식으로 푼다는 것이 핵심이다.
2. 왜 사용하는가
- 문제의 자연스러운 표현: 어떤 문제는 그 자체가 재귀 구조다. 트리 순회, 그래프 탐색 같은 작업은 재귀로 표현하는 편이 직관적이다.
- 간결성과 가독성: 반복문을 쓸 때보다 코드가 짧고 읽기 쉽다. 특히 복잡한 로직을 처리할 때 유용하다.
- 분할 정복(Divide and Conquer) 구현이 쉽다: 재귀는 분할 정복 전략의 핵심 요소다. 문제를 작은 부분 문제로 나누어 해결하는 방식을 그대로 효과적으로 구현한다.
3. 동작 원리
재귀 호출은 함수 실행 스택(Stack)이 관리한다. 함수가 호출될 때마다 스택에 새 프레임이 쌓이고 지역 변수와 반환 주소 같은 정보가 여기 저장된다. 재귀 함수가 자기 자신을 부를 때마다 프레임이 하나씩 늘어나며 종료 조건에 도달하면 쌓인 프레임이 차례로 제거되면서 결과 값을 반환한다.
4. 코드 예제 (Python)
python
def factorial(n):
"""팩토리얼 계산 함수 (재귀적 구현)"""
if n == 0: # 종료 조건
return 1
else:
return n * factorial(n-1)
print(factorial(5)) # Output: 1205. 시간 복잡도와 성능
재귀 함수의 시간 복잡도는 문제의 크기와 재귀 호출 깊이에 따라 달라진다. 위 factorial 함수는 O(n)이다. 다만 재귀 호출이 지나치게 깊어지면 함수 실행 스택 오버플로우(Stack Overflow)가 난다.
6. 실무 사용 사례
- 트리와 그래프 알고리즘: 깊이 우선 탐색(DFS), 너비 우선 탐색(BFS) 구현에 재귀를 자주 쓴다.
- 정렬 알고리즘: 병합 정렬, 퀵 정렬처럼 분할 정복 방식의 정렬 알고리즘은 재귀로 동작한다.
- 동적 프로그래밍(Dynamic Programming): 메모이제이션으로 중복 계산을 막아 성능을 높인다.
7. 주의할 점
- 종료 조건: 모든 재귀 함수에는 반드시 종료 조건이 있어야 한다. 없으면 무한 루프에 빠진다.
- 스택 오버플로우: 재귀 호출이 과도하면 스택 오버플로우가 난다. 꼬리 재귀 최적화(Tail Call Optimization)를 지원하는 언어에서는 이 문제를 덜 수 있다. (Python은 꼬리 재귀 최적화를 지원하지 않는다.)
- 성능: 재귀는 반복문보다 느린 편이다. 특히 깊이가 깊은 재귀 호출은 오버헤드가 상당하다.
8. 핵심 정리
재귀는 함수가 자기 자신을 호출하는 프로그래밍 기법이다. 문제를 더 작은 부분 문제로 나누어 해결하고 코드를 간결하게 만든다는 장점이 있지만 종료 조건과 스택 오버플로우는 늘 확인해야 한다. 재귀의 개념과 동작 원리를 이해하면 복잡한 문제를 효율적으로 해결하는 데 도움이 된다.