[Data Structure] Tail Recursion

재귀 함수에서 마지막 동작이 재귀 함수를 호출하는 상태일때 이를 Tail Recursion이라 한다.

재귀 함수에서 호출 반환 과정에서, 반환 할때 추가적으로 해야할것이 남아 있다면 Tail R이라 볼 수 없다.

Tail Recurion Example

void fun(int n)
{
	if (n > 0)
	{
		printf("%d", n);

		fun(n - 1);
	}
}
fun(3);

코드를 살펴보면 함수 내부동작 후 리턴하는 과정(내림차순)에서 추가적인 행동없이 곧바로 리턴할 수 있다면 Tail R인것이다.

만약 fun(n-1)이 아니고 return fun(n-1) + n 이런식이라면, 내림차순의 과정(복귀)에서 n을 더하기 때문에 이는 Tail R 이 아니다.

또한 복귀과정 말고도 저 코드 즉시의 상황을 보자면, fun(n-1) + n의 add연산을 하기위해 n은 피연산자인 fun(n-1)의 결과가 나올때까지 어쩌지 못하는 대기 상태에 놓이게 된다고 볼 수 있다. 이 또한 Tail R가 아니라는 근거가 된다.

Tail Recursion vs Loops:

• Tail R은 쉽게 반복문으로 변환될 수 있다. 그 반대도 마찬가지이다.
• 반복문으로 표현하거나 기존의 코드도 모두 시간복잡도 O(n)의 크기를 갖는다.
• 하지만 공간복잡도의 경우 tail O(n), loop O(1)을 각각 가지게 된다. 즉 재귀함수의 경우 공간 효율이 좋지 못하다.
• 공간 비효율을 없애기 위해 tail R를 loop로 바꾸는것이 좋다.
• 다만, 일부 컴파일러의 경우 자체 계산에 따라 tail R를 loop로 변환하여 컴파일할 수도 있다. (공간을 효율적으로 실행시키기 위해)

뿐만 아니라 모든 재귀함수도 또한 반복문으로 상호 변환이 가능하다.