재귀(Recursion)는 컴퓨터 과학에서 함수나 절차가 자기 자신을 직접 혹은 간접적으로 호출하는 프로그래밍 기법 및 이론적 개념을 의미한다. 재귀 호출은 일반적으로 기저 조건(base case)과 재귀 단계(recursive step) 로 구성된다. 기저 조건은 재귀 호출을 종료시키는 조건이며, 재귀 단계는 문제를 더 작은 하위 문제로 분할하여 자기 자신을 호출한다.
주요 특징
- 자기 참조
- 함수, 메서드, 프로시저가 자신의 정의 안에서 자신을 호출한다.
- 스택 프레임 사용
- 각 재귀 호출은 호출 스택에 새로운 프레임을 추가한다. 기저 조건에 도달하여 반환될 때마다 스택 프레임이 차례로 해제된다.
- 종결성 보장
- 모든 재귀 정의는 반드시 기저 조건을 포함해야 하며, 그렇지 않을 경우 무한 재귀가 발생하여 스택 오버플로우(Stack Overflow) 오류가 발생한다.
일반적인 활용 사례
| 분야 | 예시 |
|---|---|
| 정렬 알고리즘 | 퀵 정렬(QuickSort), 병합 정렬(MergeSort) |
| 트리 탐색 | 전위(preorder), 중위(inorder), 후위(postorder) 순회 |
| 수학적 계산 | 피보나치 수열, 팩토리얼, 거듭제곱 |
| 탐색/백트래킹 | 미로 찾기, 퍼즐 풀이(예: N-Queens) |
| 언어 파싱 | 재귀 하향 파서(Recursive‑descent parser) |
구현상의 고려사항
- 스택 깊이 제한: 대부분의 실행 환경은 호출 스택에 제한을 두고 있다. 깊이가 큰 재귀는 반복문으로 변환하거나 꼬리 재귀(tail recursion) 최적화를 활용한다.
- 꼬리 재귀 최적화(TCO): 일부 컴파일러·인터프리터는 마지막 연산으로 자기 자신을 호출하는 꼬리 재귀를 반복문 형태로 변환하여 스택 사용을 최소화한다. 언어별 지원 여부가 다르다(예: Scheme, 일부 C 컴파일러, Python은 기본적으로 지원하지 않음).
- 메모리 사용: 재귀 호출 시 각 프레임이 매개변수, 지역 변수, 반환 주소 등을 저장하므로 메모리 사용량이 증가한다. 메모리 효율이 중요한 경우 반복 구조로의 변환을 고려한다.
이론적 배경
- 재귀 정의와 수학적 귀납법: 재귀 함수의 정확성 증명은 종종 수학적 귀납법을 사용한다. 기저 조건이 올바르게 동작함을 보이고, 재귀 단계가 기저 조건이 성립하는 경우에도 올바르게 동작함을 증명한다.
- 데카르트의 자기참조 원리와 연결되는 논리적 개념으로, 컴퓨터 과학에서는 고정점 연산자(fixed‑point combinator)를 이용해 이름 없는 재귀 함수를 정의한다(예: 람다 계산에서 Y‑조합자).
언어별 재귀 지원 현황 (대표적인 예)
- C / C++: 함수 내에서 자유롭게 재귀 호출 가능. 최적화 옵션에 따라 TCO가 적용될 수 있다.
- Java: 메서드 재귀 호출 지원. JVM의 스택 크기 제한에 주의.
- Python: 재귀 호출 가능하지만 기본 재귀 깊이 제한이 1000 수준이며,
sys.setrecursionlimit()로 조정 가능. - Haskell: 함수형 언어로, 꼬리 재귀 최적화가 자동으로 적용되는 경우가 많다.
- Lisp 계열 (Scheme, Common Lisp): 재귀와 꼬리 재귀 최적화를 강조하는 설계 철학을 갖는다.
장점 및 단점
| 장점 | 단점 |
|---|---|
| 구현이 직관적이며 코드가 간결해질 수 있다. | 호출 스택 사용으로 메모리 오버헤드가 발생할 수 있다. |
| 복잡한 문제를 동일한 구조로 분할하여 해결한다. | 기저 조건을 누락하거나 잘못 설계하면 무한 재귀가 발생한다. |
| 수학적 귀납법을 통한 증명과 연계가 용이하다. | 일부 환경에서는 성능 저하가 발생한다(특히 깊은 재귀). |
결론
재귀는 알고리즘 설계와 구현에서 핵심적인 기법 중 하나이며, 적절히 사용될 경우 문제를 높은 수준의 추상화로 표현할 수 있다. 다만, 실행 환경의 스택 제한 및 성능 특성을 고려하여 필요에 따라 반복문으로 대체하거나 꼬리 재귀 최적화를 활용하는 것이 바람직하다.
