최근에 최적화 관련된 글을 찾아보다가 TCO(Tail Call Optimization) 라는 개념을 접하였습니다. 궁금해서 알아보니 재귀와 관련된 메모리 최적화 방법으로서 이번 글에서는 이에 대한 내용을 설명해보겠습니다.
먼저 Tail Call이란, 가장 대표적인 예로 들자면 재귀함수에서 함수의 호출을 해당 루틴의 마지막 행위로 수행하는 것입니다. 코드로 살펴볼까요?
function recursion(n) {
if (n === 0) {
return 0;
}
return n + recursion(n - 1);
}
recursion(5); // 15간단하게, 5이하의 자연수의 합을 구하는 재귀함수입니다. 그런데, 위 구조는 해당 재귀함수가 호출 된다면 메모리 스택(JS일 경우 콜스택)에 계속 쌓이게되는 로직입니다.
>> recursion(5)
>> recursion(5) >> recursion(4)
>> recursion(5) >> recursion(4) >> recursion(3)
>> recursion(5) >> recursion(4) >> recursion(3) >> ..
>> ..
>> recursion(5) >> recursion(4) >> recursion(3) >> ..
>> recursion(5) >> recursion(4) >> recursion(3)
>> recursion(5) >> recursion(4)
>> recursion(5)바로 함수가 반환될 때, 실행 컨텍스트가 존재한다면 차례대로 스택에 쌓이게 됩니다. 그리고 실행 컨텍스트를 연산하면서 반환해나가게 되겠죠. 하지만 다음과 같이 함수를 구성한다면 결과는 다르게 보여집니다.
function recursion(n, total=0) {
if (n === 0) {
return total;
}
return recursion(n - 1, total + n);
}
recursion(5); // 15단순히, return 값에 추가적인 실행 컨텍스트가 존재하지않고, 함수만 호출하는 구조입니다. 이 때, 메모리 스택에는 다음과 같이 보여집니다.
>> recursion(5)
>> recursion(4)
>> recursion(3)
>> recursion(2)
>> recursion(1)
>> recursion(0)단순히 굳이 메모리에 쌓이지 않고, 함수가 호출된 상위 함수의 반환 주소만 넘겨받아서 실행되게 됩니다.
하지, 이에 대해서 이에 대해서 무조건 지키라는 말은 아닙니다. 왜냐하면 다음 링크를 확인하게 되면, 현재 브라우저별로 TCO를 적용되는지 확인할 수 있는데, Node를 포함한 대부분의 브라우저가 지원하고 있지 않은 것을 확인할 수 있습니다. 'use strict'; 를 파일 상단에 작성하고 해당 파일을 --harmony_tailcalls 옵션과 함께 실행하면 된다고 하지만... 항상 빨라지는 것을 보장하는 것은 아니니 참고하도록 합시다.
추가적인 여담으로 Python 은 TCO를 자체적으로 지원하지 않을뿐더러, 혹, 타사 모듈을 사용하여 TCO를 사용할 수는 있지만, 스택 추적이 제거/변경 되어 디버깅이 어려워지므로, 명시적 반복을 사용하는 것을 선호한다고 합니다.
이처럼 모든 프로그래밍 언어에 TCO가 적용된 것도 아니니 참고하도록 합시다.
Reference
