개념
TCO (Tail Call Optimization)은 재귀 함수 호출을 최적화하기 위해 컴파일러 및 프로그래밍 언어에서 사용되는 기술입니다. 많은 프로그래밍 언어에서 함수가 다른 함수를 호출하면 호출자가 새 스택 프레임을 콜스택으로 push 합니다. 이 스택 프레임에는 로컬 변수 및 반환 주소와 같은 호출자의 상태 정보가 포함되어 있으므로 프로그램은 호출된 함수가 반환될 때 컨트롤을 반환할 위치를 알 수 있습니다.
그러나 Tail Call에서는 호출 함수의 마지막 작업이 호출을 수행하는 것이며 호출 후 추가 처리를 수행하지 않습니다. 이 경우 콜스택에 새 스택 프레임을 push 할 필요가 없으며 프로그램에서 현재 스택 프레임을 재사용할 수 있습니다. 이렇게 하면 메모리를 절약하고 Stack Overflow 오류 리스크를 줄일 수 있습니다.
TCO는 모든 언어에서 제공되지 않지만 Scheme, Standard ML 및 Haskell과 같은 함수형 언어에는 이 기능이 존재합니다. JavsScript에서 TCO는 기본적으로 지원되지 않지만 이 기능을 포함하도록 ES6에 대한 제안이 있습니다.
모든 Tail Call이 TCO에 적격인 것은 아니며 일부 언어 별 규칙 및 제약 조건을 고려해야 합니다.
예제 - Factorial
팩토리얼을 계산할 때 TCO를 사용할 수 있습니다.
type TrampolineType<T> = T | (() => TrampolineType<T>);
function trampoline<T>(f: () => any): T {
let res = f();
while (typeof res === 'function') {
res = res();
}
return res;
}
function factorial(n: number, acc = 1): TrampolineType<number> {
if (n === 0) {
return acc;
}
return () => factorial(n - 1, n * acc);
}
console.log(
'trampoline(() => factorial(10)): ',
trampoline<number>(() => factorial(10)),
);
트램펄린은 재귀 호출 시 Stack Overflow 오류를 방지하는 데 사용되는 기술로, 콜스택을 사용하여 함수 호출을 추적하는 대신 결과를 얻을 때 까지 함수를 반복적으로 적용하여 작동합니다.
기본 아이디어는 최종 값이 반환될 때 까지 함수를 반환하는 함수를 만드는 것입니다. 함수를 재귀적으로 호출하는 것이 아니라 반환된 함수를 호출하고 최종값을 얻을 때 까지 이 과정을 반복합니다. 이렇게 하면 스택 프레임이 재사용되고 Stack Overflow 에러를 피할 수 있습니다.
TCO는 특히 크고 복잡한 재귀 함수에서 성능에 큰 영향을 미칠 수 있는 기술입니다.
'컴퓨터 공학 > JavaScript' 카테고리의 다른 글
Understanding the Token Bucket Algorithm in JavaScript (0) | 2022.12.21 |
---|---|
pkg 모듈 실행 시 "(0, assert_1.default)(!this.bar)" 에러 발생하는 경우 (0) | 2022.12.04 |
VSCode에서 JavaScript CommonJS의 export 객체 속성들 <Find Reference>에 검색되지 않는 문제 (1) | 2022.09.06 |
Cloudflare Workers와 Notion API로 유저 데이터 관리하기 (0) | 2022.08.14 |
JavaScript로 interface 모사하기 (0) | 2022.08.06 |