Tail Call Optimization

Notice

Recent Posts

Recent Comments

Link

« 2026/05 »
일	월	화	수	목	금	토
					1	2
3	4	5	6	7	8	9
10	11	12	13	14	15	16
17	18	19	20	21	22	23
24	25	26	27	28	29	30
31

Tags more

Archives

Today

Total

관리 메뉴

로또

Tail Call Optimization 본문

Tail Call Optimization

아롱로또 2023. 9. 12. 18:53

작성 이유

퀵 정렬과 병합 정렬을 비교하던 중 퀵 정렬의 장점으로 TCO를 알게 되어 정리하려고 한다.

정의

재귀 함수의 성능을 향상시키고 Stack Overflow를 방지하는 최적화 기술

Tail Call

함수의 호출이 끝난 후 현재 함수에서 추가 연산을 요구하지 않는 함수 형태이다.

어떠한 함수가 return 하기 직전에 호출되는 것을 의미한다.

아래와 같은 factorial 함수는 factorial(n-1) 함수 호출 이후에 n을 곱해주는 연산이 필요하므로 Tail Call이 아니다.

int factorial(int n) {
    if (n == 1) return 1;
    return n * factorial(n - 1);
}

factorial 함수를 다음과 같이 수정해보자.

tail_factorial(n-1) 호출 이후에 해당 함수에서는 별다른 연산없이 즉시 return하므로 Tail Call이다.

int tail_factorial(int n, int acc) {
    if (n == 1) return acc;
    return tail_factorial(n - 1, acc * n);
}

Tail Call Optimization

Tail Call 함수에서 새로운 Stack Frame을 생성하지 않고 동일한 Stack Frame에서 값만 대체하여 별도 공간의 할당없이 재사용하는 것이다.

다음은 factorial함수를 Visual Studio의 디버거를 사용해 호출 스택을 조사한 결과이다.

호출 스택이 점점 쌓이는 것을 볼 수 있다.

다음은 tail_factorial 함수의 경우이다.

분명 tail_factorial 함수를 재귀적으로 호출했음에도 호출 스택이 늘어나지 않는 모습을 볼 수 있다.

이처럼 TCO가 적용되면 Stack Overflow를 방지할 수 있으며 메모리를 효율적으로 사용할 수 있다.

퀵 정렬 함수 또한 함수의 마지막에서 추가 연산을 요구하지 않는 Tail Call이고, 때문에 TCO를 적용받을 수 있다.

Visual Studio에서 TCO 발생시키기

환경에 따라서 TCO를 지원하지 않을 수도 있어서 많은 자료를 참고했었다. 간단하게 정리하면 다음과 같다.

테스트 코드

#include <iostream>

using namespace std;

int factorial(int);
int tail_factorial(int, int);

int factorial(int n) {
    if (n == 1) return 1;
    return n * factorial(n - 1);
}

int tail_factorial(int n, int acc) {
    if (n == 1) return acc;
    return tail_factorial(n - 1, acc * n);
}

int main()
{
    // cout << factorial(5) << endl;
    cout << tail_factorial(5, 1) << endl;
    return 0;
}

프로젝트 - 속성 - C/C++ - 최적화 - 최적화(속도 우선)(/Ox) 선택