TCO (Tail Call Optimization) 개념 및 예제

"Pikachu Cutaway Drawing" - Midjourney

개념

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는 특히 크고 복잡한 재귀 함수에서 성능에 큰 영향을 미칠 수 있는 기술입니다.