[C++] Tail Call Optimization, Tail Recursive Elimination

함수호출에 관한 최적화 기법으로 Tail Call Optimization, Tail Recursive Elimination이라는것이 있다.

글마다 뭔가 조금씩 차이가 있는것 같긴한데, 기본적인 이해를 위해 잘 정리된 글들이 있어 먼저 소개한다.

 

https://tiger1710.tistory.com/56

Tail Call Recursion

https://hongjw1938.tistory.com/192

알고리즘 - Quick(퀵) vs Merge(병합) 정렬(+TCO, 참조 지역성)

정리하자면 아래와 같다. (개인적인 이해를 위한 보기 불편할 수도 있다. 내 티스토리내의 글들이 대부분 그렇다)

 

return 하기 직전에 연산없이 함수'만' 호출하는 경우를 Tail Call이라고 한다. (콜스택에 안쌓이는 연산이라면 상관없다)

이렇게 Tail Call을 하는게 왜 좋은가?를 따져보자.

 

함수의 마지막에서 함수를 호출하게 되면, 다시 호출한 함수로 되돌아 올 필요가 없기 때문에 이 호출한 함수를 Stack에 저장하고 있을 이유가 없다. 만약 Tail Call이 아니라면, 즉 되돌아가서 해야할 어떠한 작업(연산)이 있다면 계속 유지시켜줘야 하니 스택에서 삭제하면 안되며 결국 계속 쌓이게 될 것이다.

이렇게 Tail Call을 이용하면, 이전의 호출한 함수에 대한 스택프레임을 유지할 필요가 없기 때문에 스택공간을 효율적으로 사용할 수 있다. 이러한 최적화를 Tail Call Optimization 이라고 한다.

 

함수'만' 호출해야 한다는게 무슨 말이냐면, return f(n); 같은 경우를 말한다.

return n * f(n-1); 이런식으로 *같은 연산이 있으면 안된다. 그러면 다시 되돌아와야하기 때문에 해당 return문을 호출한 함수가 계속 스택에 할당되어있어야 한다.

 

return 문에 호출할 함수가 자기자신이라면 이제 Tail Recursion(꼬리 재귀)이 되는 것이다.

꼬리 재귀형태의 코드가 짜여졌다면 Tail Recursion Elimination이라는 최적화 기법도 적용이 가능해진다.

자기자신을 호출하는 것이기 때문에, 스택프레임은 유지한 채 goto문을 통해 마치 for문처럼 작동하는 로직이 내부적으로 구성되어질 수 있다.

 

즉! 우리는 코드를 자기자신을 다시 호출하는 재귀형식으로 짰지만, 컴파일시 내부적으로는 추가적으로 함수호출하는것이 아니라 누적되는 값을 갱신 후, goto문을 통해 다시 함수의 start부분으로 되돌아가 함수를 또 수행하는 것이다. (호출하는 것이 아니다!)

추가적으로 호출하는 것이 아니기 때문에 별도의 스택프레임을 생성할 필요가 없기 때문에 굉장히 효율적이다.

별도의 스택프레임을 생성할 필요가 없다는것은 매우 큰 이점을 지닌다.

스택메모리를 아낀다는 것 뿐만 아니라 추가로 호출한 함수(n번째 함수)로 갔다가 다시 되돌아오는 과정(n-1번째 함수)을 거칠필요가 없는것이다. 이렇게 왔다갔다 하는것 또한 그 횟수가 많아지면 절대 무시하지 못할 비용이다.

 

다만, 이러한 최적화기법들은 모든 곳에서 지원하는것은 아니다.

visual studio에선 지원한다고 한다.