꼬리 재귀란 무엇인가?
꼬리 재귀(tail recursion)는 재귀 호출이 함수의 마지막(꼬리) 문장으로 실행되는 재귀를 의미합니다. 즉, 재귀 호출이 끝나고 반환된 이후에 더 이상 수행할 작업이 남아 있지 않은 경우를 말합니다. 이러한 특성 덕분에 컴파일러가 코드를 효율적으로 최적화할 수 있어, 일반적인 재귀보다 성능 면에서 유리합니다.
꼬리 재귀 예제
다음은 n부터 0까지의 숫자를 출력하는 간단한 꼬리 재귀 함수입니다.
#include <iostream>
using namespace std;
void printN(int n) {
if (n < 0) {
return;
}
cout << n << " ";
printN(n - 1); // 재귀 호출이 함수의 마지막 문장
}
int main() {
printN(10);
}실행 결과
10 9 8 7 6 5 4 3 2 1 0
위 코드에서 printN(n - 1) 호출 이후에는 어떤 연산도 수행되지 않습니다. 재귀 호출이 곧 함수의 마지막 동작이므로, 이것이 바로 꼬리 재귀입니다.
꼬리 재귀가 유리한 이유: 스택 최적화
일반적인 함수가 호출되면 해당 함수의 복귀 주소(return address)가 스택(stack)에 저장됩니다. 재귀 호출이 깊어지면 스택 프레임이 계속 쌓여 스택 오버플로우(stack overflow)가 발생할 수 있습니다.
하지만 꼬리 재귀의 경우, 재귀 호출 이후에 남은 작업이 없기 때문에 컴파일러는 기존 스택 프레임을 재사용하는 방식으로 코드를 최적화할 수 있습니다. 대표적인 예가 꼬리 호출 제거(tail call elimination)로, 이를 통해 재귀 함수가 사실상 반복문처럼 동작하게 되어 메모리 사용량과 호출 오버헤드를 크게 줄일 수 있습니다.
꼬리 재귀가 아닌 경우: 팩토리얼
재귀로 팩토리얼을 구현할 수 있지만, 다음 코드는 꼬리 재귀가 아닙니다.
long fact(int n) {
if (n <= 1)
return 1;
return n * fact(n - 1); // 곱셈 연산이 재귀 호출 이후에 수행됨
}fact(n)의 결과값을 만들기 위해 fact(n-1)의 반환값이 필요하므로, 재귀 호출이 끝난 뒤에도 곱셈이라는 추가 작업이 남아 있습니다. 따라서 이 함수는 꼬리 재귀가 아니며, 컴파일러가 스택 프레임을 줄이는 최적화를 적용하기 어렵습니다.
팩토리얼을 꼬리 재귀로 변환하기
누적값(accumulator)을 담을 추가 매개변수를 도입하면 위 함수를 꼬리 재귀 형태로 바꿀 수 있습니다.
long fact(long n, long a) {
if (n == 0)
return a; // 누적된 결과 반환
return fact(n - 1, a * n); // 재귀 호출이 마지막 문장
}호출 시 초기값으로 fact(n, 1)처럼 1을 전달하면 됩니다. 이렇게 하면 중간 결과가 매개변수 a에 누적되고, 재귀 호출 이후에는 어떠한 연산도 남지 않으므로 완전한 꼬리 재귀가 됩니다. 결과적으로 컴파일러가 최적화를 수행하기 좋은 구조가 되어, 깊은 재귀에서도 안정적으로 동작할 수 있습니다.
정리
- 꼬리 재귀는 재귀 호출이 함수의 마지막 동작인 재귀 형태다.
- 재귀 호출 후 남은 작업이 없으므로 컴파일러가 스택 사용을 최적화할 수 있다.
- 누적 매개변수를 활용하면 일반 재귀 함수도 꼬리 재귀로 변환할 수 있다.