재귀함수란 자기 자신을 호출하는 함수를 말합니다.
코드가 짧아져 가독성을 높일 수 있다는 장점이 있지만, 스택 오버 플로우를 일으킬 수 있는 엄청난 위험성도 내재하고 있습니다.
함수를 호출할 때 함수의 입력 값(매개변수), 리턴값, 그리고 리턴됐을 때 돌아갈 위치값 등을 스택에 저장합니다. 재귀함수를 사용하면 함수가 끝나지 않은 채 연속적으로 함수를 호출하므로 스택에 메모리가 쌓이게 됩니다. 이 때문에 스택의 최대 크기 이상의 메모리가 쌓이게 되면 스택 오버 플로우가 일어나게 됩니다. 또한, 잦은 점프의 반복으로 성능이 저하될 위험도 가지고 있습니다.
이런 재귀의 특징을 정리하자면 다음과 같습니다.
- 무한 루프에 빠지지 않기 위해 일정한 탈출 조건이 있어야 한다.
- 코드를 단순화 할 수 있다.
- 재귀 함수는 호출 시 마다 스택 공간을 이용하므로 무리하게 호출하면 스택 오버플로우가 일어날 수 있다.
- 재귀 함수의 호출 횟수는 스택의 남은 공간과 재귀 함수의 지역 변수 사이즈에 따라 달라진다.
- 디버깅 및 실행 흐름을 파악하기 힘들다.
재귀는 장점도 있지만, 단점도 많기 때문에 사용에 주의를 기울여야 하는데, 이런 재귀함수의 단점을 보완하기 위한 꼬리 재귀라는 최적화 방법이 있습니다.
꼬리 재귀란, 재귀 호출이 끝난 후 현재 함수에서 추가 연산을 요구하지 않도록 구현하는 재귀의 형태입니다. 이를 이용하면 함수 호출이 반복되어 스택이 깊어지는 문제를 컴파일러가 선형으로 처리 하도록 알고리즘을 바꿔 스택을 재사용할 수 있게 됩니다.(더이상 값이 변할 여지가 없으므로 스택을 덮어쓸 수 있기 때문) 이러한 꼬리 재귀를 사용하기 위해서는 컴파일러가 이런 최적화 기능을 지원하는지 먼저 확인해야 합니다. (visual studio나 gcc는 지원합니다.)
일반적인 재귀함수와 꼬리 재귀함수를 비교하면서 설명하겠습니다.
이는 모두가 흔히 알고있는 재귀함수입니다.
컴파일러는 이 코드를 다음과 같이 해석합니다.
int Factorial(int n)
{
}
이를 실제로 실행하면
보다시피 스택이 쌓이는 모습을 볼 수 있습니다.
그렇다면 꼬리 재귀함수를 사용했을 때는 어떨까요?
int FactorialTail(int n, int acc) // acc : accumulator의 약자
{
return FactorialTail(n - 1, acc * n); // 일반 재귀에서의 n * Factorial(n-1)와 달리 반환값에서 추가 연산을 필요로 하지 않음
}
int Factorial(int n)
{
}
일반적인 재귀함수를 꼬리 재귀함수로 바꿨을 때입니다.
일반 재귀와의 큰 차이점은 반환값에서 추가 연산을 필요로 하지 않는다는 점입니다.
<일반 재귀함수>
호출 : Factorial(3)
3 * Factorial(2)
3 * ( 2 * Factorial(1) )
3 * (2 * 1)
3 * 2
6
반환하면서 계산하는 재귀함수에 비해,
꼬리 재귀함수는 acc 변수에 계산한 값을 저장한 후 값을 한번에 반환합니다.
이와같은 특징을 가진 꼬리 재귀함수를 컴파일러는 다음과 같이 해석합니다.
함수의 내용이 선형적으로 바뀐 것을 확인할 수 있습니다.
실제 동작 또한 스택을 한번 호출하는 것으로 끝납니다.
가독성을 높여주는 장점을 버리고싶지 않다면 한번쯤 꼬리재귀 사용을 고려해볼만하다고 생각합니다.
위에서 말씀드렸다시피 꼬리재귀를 사용하기 위해서는 컴파일러에서 이런 최적화 기능을 지원하는지 반드시 확인해야합니다.
비주얼의 경우에는 속성->C/C++->최적화->최적화->/O1 이상으로 체크(저는 Ox로 체크했습니다.)
하지만 최적화 설정을 바꾸면 여러가지 설정을 바꿔야 할것입니다.....(개발 환경에 따라 다르겠지만 저의 경우에는 디버그 정보 형식이나 런타임 오류검사를 바꿔야했습니다.)