꼬리 재귀 Tail-recursion Optimization
재귀호출을 함수의 마지막에 사용하면 컴파일러가 컴파일시에 최적화해주는 코딩 방법이죠.
C나 C++ 말고도 많은 언어에서도 지원하고 있습니다(OCaml, F#,Ruby, JAVA, ...)
예를 들어
int factorial(int n){
if(n==1) return 1;return n*factorial(n-1);}
라고 작성하고, factorial(100000) 이라고 호출하도록 한 뒤에 릴리즈 모드에서 컴파일해 봅시다.
스택 오버플로우가 날 겁니다.(안 난다면 n을 더 늘려야겠죠. 언젠가 납니다)
하지만
int factorial_tail_rec(int n, int acc){
if(n==1) return acc;return factorial_tail_rec(n-1, acc * n);}
int factorial(int n){
return factorial_tail_rec(n, 1);}
라고 작성한 뒤에 똑같이 하면, 스택 오버플로우가 나지 않습니다.
컴파일러는 위 소스를 자동으로 다음과 같이 바꾸어 주기 때문이죠.
int factorial_tail_rec(int n){
int acc=1;do{if(n==1) return acc;acc= acc*n;n=n-1;}while(1);}
이것이 가능한 이유는 재귀호출이 factorial_tail_rec의 마지막에서 일어나기 때문입니다.
즉 함수의 마지막에 재귀호출이 들어가면, 호출이 끝난 이후에 리턴값이 변할 여지가 없으니까,
스택에 새로운 인자들을 추가하는 것이 아니라, 기존 스택에 그냥 덮어씌워 버리는 거랍니다
그렇다면 처음의 factorial 함수에는 왜 적용되지 않을까요?
C++ 규칙상, 처음 함수는 다음의 구문과 완전히 일치합니다. 계산식의 중간에 함수 호출이 일어나면
그 값을 이름 없는 임시 변수에 저장하기 때문입니다.
int factorial(int n){
if(n==1) return 1;int temp=factorial(n-1);return n*temp;}
그래서 위 함수는 꼬리 재귀 최적화가 적용되지 않는 것입니다.
댓글 0