꼬리 재귀(tail recursion)

꼬리 재귀(tail recursion)

Intro.

꼬리 재귀가 있기에 함수형 언어에서 매개변수에 상태를 저장하며, 재귀를 할 때 최적화 된다!
꼬리 재귀 설명을 처음 들었을 때는 그냥 프로그래밍 기법이지 않을까 했는데 함수형 언어에서는 최적화를 지원 한다고 한다

설명

재귀 함수의 한 종류로, 함수가 반환하는 값이 마지막에 재귀 호출하는 함수에서 계산되는 경우를 말합니다.
일반적인 재귀 함수에서는 함수 호출이 스택에 계속 쌓이게 되는데, 이러한 스택의 쌓임이 많아질 경우 메모리를 많이 사용하고 성능에 영향을 미칠 수 있습니다.

하지만 꼬리 재귀는 함수 호출 후 더 이상 수행할 작업이 없는 경우, 이전 호출 스택 프레임을 재사용하고 추가적인 스택 프레임을 쌓지 않는 방식으로 최적화합니다.
이를 통해 메모리 사용량을 최적화하고 성능을 향상시킬 수 있습니다.

예를 들어, 다음과 같은 일반적인 재귀 함수를 보겠습니다.

def factorial(n):     if n == 0:         return 1     else:         return n * factorial(n-1) 

이 함수는 각 호출 시 n-1의 값을 인자로 넘겨 재귀 호출을 수행합니다.
이 경우, 함수가 반환하는 값인 n * factorial(n-1)이 마지막에 재귀 호출하는 함수에서 계산됩니다.

하지만 이 함수는 꼬리 재귀로 최적화할 수 있습니다.

def factorial(n, result=1):     if n == 0:         return result     else:         return factorial(n-1, n*result) 

이 함수에서는 추가적인 인자 result를 이용하여 이전 결과값을 계속 업데이트합니다. 이전 호출 스택 프레임을 재사용하면서도 결과값을 업데이트하는 방식으로 최적화합니다.

함수형 언어는 꼬리 호출 최적화(TCO, Tail Call Optimization)를 지원한다

TCO는 꼬리 재귀를 이용하여 함수를 호출할 때, 현재 스택 프레임을 유지하면서 새로운 함수를 호출하는 방식으로 최적화합니다.
이렇게 하면 스택을 매번 새로 쌓지 않고 이전 스택 프레임을 재사용하므로, 메모리 사용량을 줄일 수 있습니다.

즉 꼬리 재귀 호출을 하게 되는 경우, 이를 콜 스택으로 사용하지 않고, 반복문 형태로 최적화하여 실행 시간 및 메모리 사용량을 줄일 수 있다

그러나 TCO를 지원하지 않는 언어의 경우, 꼬리 재귀를 사용하면 일반적인 재귀 함수처럼 스택에 계속해서 쌓이므로, 스택 오버플로우(stack overflow) 등의 문제가 발생할 수 있습니다.

따라서 꼬리 재귀를 최적화하는 언어에서는 TCO를 지원하여 이 문제를 해결합니다.