[CS] TCO (Tail Call Optimization)

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

tail call

해당 함수가 호출될 때, 마지막으로 수행되어 현재 함수의 스택 프레임의 할당 해제가 일어나기 직전의 수행되는 경우를 의미한다.

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;
}