[CS] TCO (Tail Call Optimization)

Tail Call Optimization?
: 서브루틴의 호출을 프로시저의 마지막 행위로 수행하는 것

tail call

어떤 함수가 실행될 때, return 명령어를 만나기 전에 특정 함수가 호출되는 것을 의미한다.
해당 함수가 호출될 때, 마지막으로 수행되어 현재 함수의 스택 프레임의 할당 해제가 일어나기 직전의 수행되는 경우를 의미한다.

return func(--n);
return func(n--);

위와 같은 코드가 있다고 했을 때,
return func(--n)은 func(--n) 함수의 실행이 마지막으로 이루어지고 return이 되기 때문에 tail call 이다.
return func(n--)은 func(n) 함수의 실행이 일어난 이후, n =- 1까지 수행되고 나서 return 되기 때문에 tail call이 아니다.

tail recursion

tail call의 특수한 경우로 재귀 호출이 현재 함수(메소드)에서 마지막으로 수행되는 경우를 의미한다.

void func(int n) {
	return func(--n);
}

TCO (Tail Call Optimization)

tail call을 최적화하는 것을 말하며 컴파일러에서 지원하는 부분이기 때문에 지원되지 않는 언어나 브라우저가 있을 수 있다.
(자바, 파이썬은 TCO를 아예 지원하지 않으며, C언어 또한 TCO를 표준으로 보장하진 않는다고 한다..)

tail call optimization을 하게 되면, 마지막 호출에서 새 스택 프레임 생성을 반복하지 않고 같은 스택 프레임에서 다시 호출되는 함수의 진입점으로 GoTo하여 루틴을 진행할 수 있는 것을 의미한다.

Tail Recursion Elimination 예시

long long fatorial(int n) {
	long long result = 1;
start:
	if (n <= 1) {
		return result;
	}

	result *= n;
	n -= 1;
	goto start;
}