C 꼬리 재귀, Tail Recursion

재귀함수는 함수에서 함수가 호출되고

호출된 함수가 내부에서 다시 스스로를 호출하고

어떤 기준에 닿으면 함수를 종료시켜 리턴값을 던지고

직전에 호출된 함수가 리턴값을 받아서 다시 리턴값을 던지고

또 직전에 호출된 함수가 받아 던지고...

설명이 이해하기 어렵다면 직접 간단히 구해보면 됩니다. 아무튼 이런 함수인데

피보나치 수열을 이 재귀함수로 구현해보면 30~35번재쯤 넘어갈때부터 슬슬 시간이 오래걸리죠.

왜냐하면 함수가 호출 하고 아직 종료되지 않은 상태에서 새로운 함수를 호출할 때는 메모리(stack 영역)에 값도 쌓이고 함수 호출시 초기화하는 데이터도 계속 쌓이는데

함수가 끝나면 또 이전 함수의 위치를 찾아다니면서 리턴하고 값을 읽어내는 과정 때문에 오래걸리게 됩니다.

이러한 문제점을 해결하고자 했던 방식 중에 하나가 꼬리 재귀(Tail Recursion)입니다.

즉, 함수가 호출된 위치로 돌아갔을 때 실행할 작업이 없도록 하는 방법인데

코드구조상으로 보자면 똑같이 스스로를 호출하지만 컴파일러가 꼬리 재귀(Tail Recursion)을 인식하고 최적화(반복문)를 시켜주기 때문에 문제해결이 가능합니다.

컴파일러가 최적화를 해줄 수 있는지를 확인해야하며 지원되지 않을경우 꼬리 재귀(Tail Recursion)의 이점은 사라지게 되죠

사실상 재귀의 코드를 취하지만 컴파일러가 반복문으로 바꿔버리는 방법이라 해결법(solution)이 아니라 우회법(workaround)이라고도 말합니다.

int fibonacci_tail_recursion(int nA, int nB, int cnt, int needpoint)

{

int result;

//Exception handling of the Basecase, 베이스 케이스에 대한 예외처리

if(needpoint==1)

{

cnt = needpoint; return nA;

}

if(needpoint==2)

{

cnt = needpoint; return nB;

}

result = nA + nB;

cnt++;

if(cnt == needpoint)

return result;

fibonacci_tail_recursion(nB, result, cnt, needpoint);

}

대학시절 피보나치 수열의 재귀적 구현 과제에서 꼬리 재귀 코드도 있기에 잠깐 찾아봤습니다.