void func(int n){
    if(n < 0)
        return 0;
    else
        return n + func(n-1)
}


이런 식으로 return 에 재귀호출을 붙이면 무조건 꼬리재귀일까요?

이런 식으로 써놓은 글들이 많던데..

return에 재귀호출 붙이면 그냥 꼬리재귀?



우선 꼬리재귀를 \'잘\' 이해하려면

컴파일러 과목에서 LL 파싱에 대해서 배우면 알아요



어떠한 형태인지 보이면

E -> \'+\' NUM E 
    | ;

이게 레알 꼬리재귀죠

이걸 함수형태로 변환하면

void E(){
    if(lookahead==\'+\'){
        match(\'+\');
        NUM();
        E();
    }
}

return에 안 붙었죠?

어차피 반환형이 void니까요

위 함수 뜬금없어서 이해하기 힘들수도 있는데

+5+3+1+0+6+4+3+8+9

이런 문자열을 인식하는 함수라고 생각하시고..




근데 return에 재귀 호출하건 말건간에

꼬리재귀란


재귀 호출 때문에 다른 어떤 종속성도 생기지 않을때

꼬리 재귀라고 해요, 진짜 끝부분(꼬리)에 매달린거죠


위 예는 다음과 같이 변경 가능하고

또 이렇게 변경이 가능할때 이것을 바로 \"꼬리재귀\" 라고 불러요

/* rule: <E>
        ->        \'ADD\'        <NUM>        <E>        
        |        
;
*/
void E(){
        while(1){
                if(lookahead==ADD){
                        match(ADD);
                        NUM();
                        continue;
                }
                break;
        }
}
//

보면 재귀 호출 이였던 E() 부분이 없어지고

반복문으로 대치되었죠....

왜냐하면  재귀 호출이 끝에 매달려

다른 어떤 종속성도 만들지 않기 때문이죠



이게 핵심이에요 왜 꼬리재귀

가만 생각해보면

return에 재귀 호출을 붙이면 자연스럽게 

어떤 종속성도 만들지 않게되는걸

알수 있죠



컴파일러는 재귀 호출이 꼬리재귀라 판단이 되면 자동으로

위와 같은 반복문처럼자동으로 변경을 해준대요



단순 무식하게 return에 붙으면 꼬리재귀?

이런식으로 생각하지 마시고

저렇게 변환이 가능하다고 판단될때

컴파일러는 감지하고 변환한다는거에요



어떤 설명 보면 스택프레임에 뭐 쌓지를 않기 때문에 어쩌고.....

다 헛소리고



꼬리재귀가 반복문으로 대치되기 때문인거에요