재귀 함수 호출에 필요한 보조 공간이란?
이 글에서는 재귀 함수 호출 시 필요한 보조 공간(auxiliary space)이 얼마나 되는지 살펴보고, 일반적인 함수 호출과 어떻게 다른지 비교해 보겠습니다.
재귀 함수 예시
다음과 같은 팩토리얼 함수가 있다고 가정해 봅시다.
long fact(int n){
if(n == 0 || n == 1)
return 1;
return n * fact(n-1);
}위 함수는 자기 자신을 다시 호출하는 재귀 함수(recursive function)입니다. 이 함수를 fact(5)처럼 호출하면, 스택(stack)에는 아래와 같은 순서로 주소 정보가 차곡차곡 쌓이게 됩니다.
fact(5) --->
fact(4) --->
fact(3) --->
fact(2) --->
fact(1)
재귀 함수는 왜 O(n)의 보조 공간을 사용할까?
재귀 함수는 스스로를 계속해서 호출하기 때문에, 각 호출마다 새로운 주소와 지역 변수 정보가 스택에 추가됩니다. 따라서 함수가 재귀적으로 n번 호출된다면, 모든 호출이 반환되기 전까지 스택에 동시에 쌓여 있어야 하므로 보조 공간은 O(n)이 됩니다.
일반 함수를 반복 호출하는 경우와의 차이
그렇다고 해서 일반 함수를 n번 호출하면 무조건 공간 복잡도가 O(n)이 되는 것은 아닙니다. 일반 함수의 경우 동작 방식이 다릅니다.
일반 함수가 호출되면 그 순간에만 주소가 스택에 푸시(push)됩니다. 함수 실행이 끝나면 해당 주소는 스택에서 팝(pop)되어 호출자(invoker) 함수로 돌아가고, 그 후에 다음 함수를 다시 호출합니다.
즉, 어느 한 시점에 스택에는 단 하나의 함수 호출 정보만 존재하므로, 일반 함수를 몇 번을 반복해서 호출하더라도 보조 공간은 O(1), 즉 상수 공간으로 유지됩니다.
정리
- 재귀 함수: 모든 호출이 완료될 때까지 스택에 호출 정보가 누적되므로 보조 공간은 O(n)
- 일반 함수 반복 호출: 호출이 끝날 때마다 스택에서 제거되므로 보조 공간은 O(1)
이러한 차이 때문에 깊은 재귀 호출은 스택 오버플로우(stack overflow)를 유발할 수 있으며, 가능한 경우 반복문 기반 구현으로 변환하는 것이 메모리 측면에서 유리할 수 있습니다.