[ 개념 ] 03. Tail Call Recursion

> Tail Call Recursion

C++

제가 이번에 설명할 것은 제가 검색하다가 발견한! Tail Call Recursion 이라는 새로운 재귀?적인 방법의 코딩입니다. 기존의 재귀함수와 비교하면서 설명하도록 하겠습니다.

1. 기존의 재귀함수

먼저 기존의 재귀함수를 보도록합니다. 여기서는 가장 대표적인 피보나치 수열을 이용한 재귀함수를 살펴보겠습니다.

#include <iostram>
using namespace std;

int f(int n){
    if(n < 0) return 0;
    if(n < 2) return n;
    return f(n-1) + f(n-2);
}

int main(void){
    cout << f(4) << '\n';

    return 0;
}

뭐.. 설명할 것이 많이 없네요. f라는 함수는 피보나치 수열의 n번째 항을 값으로 리턴해주는 함수입니다. 0번째 항은 0으로 정의 하겠습니다. f(4)를 호출하게 되면 피보나치수열의 4번째 값인 ‘3’이 잘 출력되는 프로그램입니다. 여기서! f(4)가 호출되었을 때, 일어나는 과정을 살펴보면.

f(4) 호출
    f(3) 호출
        f(2) 호출
            f(1) 호출 1 리턴
            f(0) 호출 0 리턴
        f(2) 가 1 리턴
        f(1) 호출 1리턴
    f(3) 이 2 리턴
    f(2) 호출
        f(1) 호출 1 리턴
        f(0) 호출 0 리턴
    f(2) 가 1 리턴
f(4) 가 3 리턴

f(4)만 호출해도 머리로만 따라가기엔 조금 벅찹니다.. 물론 컴퓨터는 이러한 연산을 빠르게 해서 답을 잘 내주는 것이죠. 그렇다면 여기서 f(40)을 호출하면 어떻게 될까요? 콘솔이.. 쉽게 답을 내주지 않습니다. 멈춘것이 아니라 계속 연산을 진행중인 것입니다. f(4)만 호출해도 이정도의 양을 연산해야 하는데 f(40)을 호출하게되면 엄청난 양의 연산을 진행해야 하기때문입니다. 게다가 엄청난 양의 Stack공간도 사용하게 됩니다. 왜냐하면 호출 스택에 자신을 호출했던 주소를 저장해놓고 그 위치로 다시 돌아가야 하기 때문이죠. 100보다 큰 값을 호출하면 프로그램이 죽는 경우도 있을 겁니다..

2. Tail Call Recursion

2.1 Tail Call

먼저 Tail Call 이란 것을 살펴보도록 합시다. tail call 이란 말그대로 꼬리호출, 맨 마지막에서 호출한다는 뜻입니다. 예를 들어 보겠습니다.

#include <iostram>
using namespace std;

int f(int a){
    a = 0;
    return 0;
}

int foo1(int b){
    return f(b) + 1;
}

int foo2(int c){
    return f(c);
}

int main(void){
    cout << foo1(10) << '\n';
    cout << foo2(10) << '\n';

    return 0;
}

먼저 f라는 함수를 보겠습니다. f는 받은 값을 0으로 만들어 돌려주는 함수입니다. 여기서 foo1 을 보면 f(b) 를 호출하고 + 1을 한뒤에 리턴합니다. 이렇게 되면 foo1 에서 불린 f(b) 는 tail call이 아닙니다. 왜냐하면 f(b) 가 값을 리턴한 후에 다시 foo1 으로 돌아와서 + 1을 해준후에 값을 리턴해야하기 때문입니다. 반면에 foo2 를 보게되면 f(c) 를 호출하고 바로 리턴합니다. 이렇게 되면 다시 foo2로 돌아와서 작업할 필요가 없고 그냥 f(c) 의 값만 리턴하면 됩니다.

즉, Tail Call 이란건 함수를 바로 종료하기 위해서 함수의 마지막에서 함수를 호출하는 것을 말합니다. 위의 foo1 처럼 마지막에 함수를 호출했다고 다 tail call이 아니라 함수를 호출 했을 때, 함수를 호출한 함수가 바로 종료될 수 있도록 하는 기법입니다.

2.2 Tail Call Optimization

이렇게 Tail Call 을 사용하게 되면 무엇이 좋은가! 라고 생각하실 수 있습니다. 이렇게 함수의 마지막에서 함수를 호출하게 되면(다른 추가적인 일을 할 필요 없는 상태에서) 다시 이 호출한 함수로 돌아올 필요가 없어지게 됩니다. 함수에서 더 이상 할일이 없기 때문에 Stack에 저장할 필요없이 끝내도 된다는 뜻입니다..! 그리고 사용한 Stack 공간을 재사용 할 수 있게 됩니다. 이러한 기법을 Tail Call Optimiztion 이라고 하는 것입니다. 하지만 이것은 언어가 지원하는 경우에만 해줍니다...

2.3 Tail Recursion

그렇다면 Tail Recursion 이란? tail call방식으로 함수를 작성하는데 호출하는 함수가 자기자신인 재귀함수인 것입니다. 위의 피보나치 코드를 tail recursion방식으로 작성하여 보면

#include <iostream>
using namespace std;

int f(int n, int prev=0;, int next =1){
    if(not n) return prev;
    return f(n-1, next, prev + next);
}

int main(){
    cout << f(4) << '\n';
    return 0;
}

이렇게 됩니다. 함수 f 에서 마지막에 자기자신만 호출하고 아무것도 안하므로 마지막에 호출하는 tail call recursion 형식이 됩니다. f(40)까지 빠르게 구할 수 있게됩니다. 여기에 tail call optimization까지 적용한다면 Stack을 더이상 낭비하지 않고 함수안의 피라미터만 바꿈으로써 추가적인 메모리도 필요하지 않게 됩니다. wikipedia 에서는 이렇게 되면 *goto* 문의 사용과 비슷한 효과를 내며 기계어로 *JUMP*와 같은 코드가 된다고 합니다.

위의 피보나치 함수와 어떻게 다른지 살펴보면,

f(4, 0, 1) 호출
    f(3, 1, 1) 피라미터 변경 호출(추가적인 Stack공간의 사용 없음)
        f(2, 1, 2) 피라미터 변경 호출(추가적인 Stack공간의 사용 없음)
            f(1, 2, 3) 피라미터 변경 호출(추가적인 Stack공간의 사용 없음)
                f(0, 3, 5) 피라미터 변경 호출(추가적인 Stack공간의 사용 없음)
                return 3;
            return 3;
        return 3;
    return 3;
return 3;

위에서는 f(4)를 호출하게되면 총 9번의 함수호출이 있었지만 tail call recursion을 사용하니 호출이 5개로 확 줄은 것을 볼 수 있습니다. 또한 tail call optimization으로 Stack공간을 추가적으로 사용하지 않고 피라미터의 값만 변경함으로써 메모리공간도 확보되었습니다.

참고한 사이트를 첨부하며 글 마칩니다.

• https://homoefficio.github.io/2015/07/27/%EC%9E%AC%EA%B7%80-%EB%B0%98%EB%B3%B5-Tail-Recursion
• https://en.wikipedia.org/wiki/Tail_call