지난 포스팅에서 재귀함수의 개념과 간단한 예시를 정리해 보았습니다. 이번 포스팅에는 재귀 함수에 대해서 조금 더 깊게 파헤쳐 보도록 하겠습니다.
재귀 함수와 메모리 사용량 간의 관계 (javascript recursion memory leak)
재귀함수가 실행되면 함수 실행에 대한 세부 정보를 담고 있는 실행 컨텍스트 (Execution context)가 생성되며 실행 컨텍스트 스택에 쌓이게 됩니다. 재귀의 깊이가 깊어질 수록 실행 컨텍스트가 더 많이 쌓이게되고 더 많은 메모리를 차지하게 됩니다.
반복문을 사용한 함수는 단 하나의 실행 컨텍스트만 스택에 쌓이기 때문에 메모리적인 비용을 고려했을 때는 반복문을 사용하는 것이 효율적일 수 있습니다.그러나 재귀를 사용한 가독성 좋은 코드와 유지보수를 위해 재귀함수를 사용합니다. 단 재귀함수를 사용할 때 재귀의 깊이를 고려해서 사용되는 메모리를 최소화하는 것이 프로그래밍 성능을 향상시키는 방법입니다.
브라우저에서 자바스크립트 코드를 로드할 때 전역 실행 컨텍스트가 실행되고 그 이후에 함수 실행에 따른 함수 실행 컨텍스트가 스텍에 쌓이는 구조입니다.
반복적인 함수 호출로인해 메모리 스택이 넘치는 것을 스택 오버플로우(Stack Overflow)라고 합니다.
꼬리 재귀 (tail recursion in js)
꼬리 재귀를 사용하면 재귀 호출로 인한 실행 컨텍스트 호출을 최소화 할 수 있습니다. 프로그래밍 언어 중 C++, C#, Kotlin, Swift 등 자동저긍로 꼬리 재귀 최적화를 지원하며, JavaScript는 ES6 스펙에서 지원하고 있습니다.
일반적인 재귀 함수
일반적으로 사용하는 팩토리얼을 구하는 재귀 함수입니다.
// 재귀함수를 이용한 팩토리얼
function factorial(n){
if(n===1) return 1;
return n * factorial(n-1);
}
console.log(factorial(4)); // 24
console.log(factorial(5)); // 120꼬리 재귀 함수
꼬리 재귀 함수는 함수 내부에서 별도의 연산 없이 전달인자로 받은 값이 변경되어 다시 전달인자로 들어가는 형태입니다. 결과 값이 변하지 않기 때문에 기존의 스택을 덮어 씌우게 되어 스택이 넘치는 경우를 예방할 수 있습니다.
// 꼬리 재귀 함수 추가
function factorialTail(n, acc=1){
if(n===1) return acc;
return factorialTail(n-1, acc*n);
}
console.log(factorialTail(4)); // 24
console.log(factorialTail(5)); // 120일반 재귀로 구현된 factorial 함수는 재귀 호출을 하고 나서, n을 곱하는 연산이 존재하기 때문에 일반 재귀로 구현된 함수는 아래 함수와 같이 동작 합니다.
function factorial(n){
if(n===0) return 1;
let callResult = factorial(n-1);
// 재귀 호출 이후 추가적인 연산이 필요합니다.
return n * callResult;
}꼬리 최적화를 사용하면 하면 컴파일러는 코드를 아래와 같이 해석 합니다.
function factorialTail(n){
acc = 1;
do{
if(n===1) return;
acc = acc * n;
n = n - 1;
} while(true);
}이렇게 내부적으로 재귀 함수를 반복문으로 변경되어 실행이 되고, 실제 스택도 여러 번 호출하는 것이 아닌 한번만 호출 합니다.
예시
일반 재귀의 실행 과정입니다.
factorial(3); // 함수 호출
// 실행 과정 -> 연산이 처리된 이후에 결과 값을 리턴합니다.
3 * factorial(2)
3 * (2*factorialTail(1))
3 * (2*1)
3 * 2
6꼬리 재귀의 실행 과정입니다.
factorialTail(3, 1); // 함수 호출
// 실행 과정 -> 별도 연산 없이 결과값 6만 리턴합니다.
factorialTail(2, 3);
factorialTail(2, 3);
6
6
6