https://bozeury.tistory.com/entry/꼬리-재귀-최적화Tail-Recursion

재귀함수란 자기 자신을 호출하는 함수를 말합니다.

코드가 짧아져 가독성을 높일 수 있다는 장점이 있지만, 스택 오버 플로우를 일으킬 수 있는 엄청난 위험성도 내재하고 있습니다.

함수를 호출할 때 함수의 입력 값(매개변수), 리턴값, 그리고 리턴됐을 때 돌아갈 위치값 등을 스택에 저장합니다. 재귀함수를 사용하면 함수가 끝나지 않은 채 연속적으로 함수를 호출하므로 스택에 메모리가 쌓이게 됩니다. 이 때문에 스택의 최대 크기 이상의 메모리가 쌓이게 되면 스택 오버 플로우가 일어나게 됩니다. 또한, 잦은 점프의 반복으로 성능이 저하될 위험도 가지고 있습니다.

이런 재귀의 특징을 정리하자면 다음과 같습니다.

재귀는 장점도 있지만, 단점도 많기 때문에 사용에 주의를 기울여야 하는데, 이런 재귀함수의 단점을 보완하기 위한 꼬리 재귀라는 최적화 방법이 있습니다.

꼬리 재귀란, 재귀 호출이 끝난 후 현재 함수에서 추가 연산을 요구하지 않도록 구현하는 재귀의 형태입니다. 이를 이용하면 함수 호출이 반복되어 스택이 깊어지는 문제를 컴파일러가 선형으로 처리 하도록 알고리즘을 바꿔 스택을 재사용할 수 있게 됩니다.(더이상 값이 변할 여지가 없으므로 스택을 덮어쓸 수 있기 때문) 이러한 꼬리 재귀를 사용하기 위해서는 컴파일러가 이런 최적화 기능을 지원하는지 먼저 확인해야 합니다. (visual studio나 gcc는 지원합니다.)

일반적인 재귀함수와 꼬리 재귀함수를 비교하면서 설명하겠습니다.

이는 모두가 흔히 알고있는 재귀함수입니다.

컴파일러는 이 코드를 다음과 같이 해석합니다.

int Factorial(int n)

{

}

이를 실제로 실행하면