꼬리 재귀 최적화(Tail Recursion)

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

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

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

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

- 무한 루프에 빠지지 않기 위해 일정한 탈출 조건이 있어야 한다.

- 코드를 단순화 할 수 있다.

- 재귀 함수는 호출 시 마다 스택 공간을 이용하므로 무리하게 호출하면 스택 오버플로우가 일어날 수 있다.

- 재귀 함수의 호출 횟수는 스택의 남은 공간과 재귀 함수의 지역 변수 사이즈에 따라 달라진다.

- 디버깅 및 실행 흐름을 파악하기 힘들다.

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

 

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

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

int Factorial(int n)

{

if (n == 1) return 1;

return n * Factorial(n-1);

}

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

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

int Factorial(int n)

{

if (n == 1) return 1;

int result = Factorial(n - 1);

return n * result;

}

 이를 실제로 실행하면

 보다시피 스택이 쌓이는 모습을 볼 수 있습니다.

 그렇다면 꼬리 재귀함수를 사용했을 때는 어떨까요?

int FactorialTail(int n, int acc)    // acc : accumulator의 약자

{

if (n == 1) return acc;

return FactorialTail(n - 1, acc * n);    //  일반 재귀에서의 n * Factorial(n-1)와 달리 반환값에서 추가 연산을 필요로 하지 않음

}

int Factorial(int n)

{

return FactorialTail(n, 1);

}

 일반적인 재귀함수를 꼬리 재귀함수로 바꿨을 때입니다.

 일반 재귀와의 큰 차이점은 반환값에서 추가 연산을 필요로 하지 않는다는 점입니다. 

<일반 재귀함수>

호출 : Factorial(3)

3 * Factorial(2)

3 * ( 2 * Factorial(1) )

         3 * (2 * 1)

3 * 2

6

 반환하면서 계산하는 재귀함수에 비해,

<꼬리 재귀함수>

호출 : FactorialTail(3, 1)

FactorialTail(2, 3)

FactorialTail(1, 6)

6

6

6

꼬리 재귀함수는 acc 변수에 계산한 값을 저장한 후 값을 한번에 반환합니다.

이와같은 특징을 가진 꼬리 재귀함수를 컴파일러는 다음과 같이 해석합니다.

 int FactorialTail(int n)

{

int acc = 1;

do

{

if (n == 1) return;

acc = acc * n;

n = n - 1;

} while (true);

}

 함수의 내용이 선형적으로 바뀐 것을 확인할 수 있습니다.

 실제 동작 또한 스택을 한번 호출하는 것으로 끝납니다.

 가독성을 높여주는 장점을 버리고싶지 않다면 한번쯤 꼬리재귀 사용을 고려해볼만하다고 생각합니다.

 위에서 말씀드렸다시피 꼬리재귀를 사용하기 위해서는 컴파일러에서 이런 최적화 기능을 지원하는지 반드시 확인해야합니다.

 

 비주얼의 경우에는 속성->C/C++->최적화->최적화->/O1 이상으로 체크(저는 Ox로 체크했습니다.)

 gcc의 경우에도 비슷하게 설정하면 됩니다. (참고 http://yumere.tistory.com/69)

 하지만 최적화 설정을 바꾸면 여러가지 설정을 바꿔야 할것입니다.....(개발 환경에 따라 다르겠지만 저의 경우에는 디버그 정보 형식이나 런타임 오류검사를 바꿔야했습니다.)

 자세한 사항은 https://msdn.microsoft.com/ko-kr/library/958x11bc.aspx를 참고해주시길 바랍니다.