Tech.log/알고리즘
[꼬리 재귀(Tail Recursion)]
SpaciousKitchen
2021. 5. 18. 22:43
재귀
하나의 함수에서 자신을 호출하여 작업을 수행하는 방식으로 문제를 푼다.
함수는 호추할때 함수의 입력값,리턴값,돌아갈 위치 값들을 스택에 저장한다.
재귀 함수를 사용하면 함수가 끝나지 않은 채 함수를 계속해서 호출함으로 스택에 메모리가 쌓이게 되고 오버 플로우가 발생한다.
이러한 단점을 보완하기 위해 꼬리재귀를 사용한다!
꼬리재귀란 ?
재귀호출이 끝난 후, 현재 함수에서 추가 연산을 요구하지 않도록 구현하는 재귀의 형태이다.
함수 호출이 반복되어 스택이 깊어지는 문제를 컴파일러가 선형으로 처리하여 재사용 가능하다.
//일반 재귀 예시
int Factorial(int n)
{
if (n == 1) return 1;
return n * Factorial(n-1);
}
//꼬리재귀 예시
int FactorialTail(int n, int result)
{
if (n == 1) return result;
return FactorialTail(n - 1, result * n);
}