Tail Call

Tail Call은 어떠한 함수가 Return 명령어를 만나기 바로 직전에 호출 되는것을 뜻한다.

이때의 직전, 혹은 마지막이란 위치 개념은 컴파일 이전의 코드에서의 개념이 아닌, 실제 스택 프레임의 할당 해제 가 일어나기 직전의 위치를 뜻한다.

그러므로 다음과 같은 경우는 코드의 마지막에 위치하지만 Tail Call에 해당하지 않는다.

e.g.

return func(n--);  // 꼬리 호출이 아니다. (호출이 일어난 뒤, n의 감소가 이루어진다)
// 만약 위 코드가 `return func(--n)` 였다면, 꼬리 호출이다.

TCO

TCO(Tail Call Optimization)는 마지막 호출에서 Call (Tail call) 을 하는경우, 새로운 스택 프레임 생성을 반복 하지 않고

같은 스택 프레임 내에서 다시 호출되는 함수의 진입점으로 Jump 하여 루틴을 진행할 수 있는것을 뜻한다(스택 프레임의 재사용 안전성).

그리고 Recursion 즉, 자기 자신을 호출하는 함수가 명령어의 가장 마지막에 위치할 때 이것을 Tail Recursion이라고 한다.

Tail Recursion Elimination

TCO(Tail Call Optimization)의 특별한 경우인 Tail Recursion Elimination 은 어떠한 함수가 꼬리재귀에 해당 할 때,

이를 반복문의 형태로 재구성 할 수 있는것을 뜻한다.

많이 착각하는 부분은, 꼬리 재귀의 형태로 구현이 되면 Tail Recursion Elimination이 된다고 생각하는 것인데,

이는 재구성 할 수 있다 라는 것이지 실제 컴파일러에서 최적화를 진행하지 않으면 일반적인 재귀와 마찬가지로 일반적인 Call이 이루어지게 된다.

Reference

• http://wiki.c2.com/?TailRecursion
• http://wiki.c2.com/?TailCallOptimization