꼬리 재귀 최적화 (Tail Call Optimization)

코딩테스트를 공부하다가, 그리고 text에 애니메이션 효과를 넣는

재귀함수를 작성하던 중, AI의 도움으로 TCO란 개념을 알게 되었다.

꼬리 재귀 최적화는 재귀 호출로 생기는 스택 오버 플로우를 방지하고, 메모리 사용을 효율적으로 만든다.

자바스크립트에서는 es6 strict 모드에서 지원하도록 명세되어 있는데, 아직 지원하는 브라우저가 많지는 않은 것 같다.

일반 재귀

꼬리 재귀

함수의 마지막 연산을 재귀함수호출로 끝내는 방식을 꼬리재귀라고 한다.

함수 스택 프레임이 필요 없어져서 메모리 사용을 최적화한다!

자바스크립트에서 꼬리재귀를 구현하는 방법은 트램폴린 기법을 사용하는 것이다.

이 방법에서는 factorialTCO 함수가 직접 결과를 반환하는 대신 함수를 반환한다.

trampoline 함수는 이 반환된 함수들을 계속 실행하여 최종 결과를 얻는다.

함수형 프로그래밍에서 주요한 기법이라고 하는데, 기존 재귀 함수의 단점(스택 오버플로우)을 해결한다는 점에서 흥미롭다. 사실 코드만 봤을 때 직관적으로 이해가 가지 않아서 헤맬 때 한번 더 찾아봐야겠다.