이항계수의 공식.


    얼추 코드로 옮기면 아래처럼 된다. (0 <= k <= n)

    int f( int n, int k ) {
        return factorial( n ) / ( factorial( k ) * factorial( n - k ) )
    }


    일단 재귀로 바꿔보자...


    f(n, 0)는 n! / ( 0! * n! ) = n! / n! = 1

    코드에 적용하면...

    int f( int n, int k ) {
        if ( k == 0 )
            return 1;
        else
            return factorial( n ) / ( factorial( k ) * factorial( n - k ) )
    }


    f(n, k)는 (n!) / (k! * (n-k)!) = ((n-1)! / ((k-1)! * (n-k)!)) * n / k = f(n-1, k-1) / n * k

    코드에 적용하면...

    int f( int n, int k ) {
        if ( k == 0 )
            return 1;
        else
            return f( n - 1, k - 1 ) * n / k;
    }

    완성...


    이제 이걸 꼬리재귀로 바꿔야 하는데...

    함수 반환값을 즉시 반환해야하니까... 반환값에 n을 곱하고 k로 나누는 연산을 없애야 한다.


    위 코드에서 결과값이 담긴 인자를 추가하고 마지막에 결과값을 반환하도록 바꾸면...

    int f( int n, int k, int a = 1 ) {
        if ( k == 0 )
            return a;
        else
            return f( n - 1, k - 1, a * n / k );
    }

    그런데 이 코드는 제대로 된 값을 내놓을 수 없다... f(5, 2)로 호출하면 f(4, 1, 2)를 호출하고, 얘는 f(3, 0, 8)을 호출한다... 10이 나와야 되는데...ㅜㅜ


    그래서 인자를 하나 더 추가했다. 나누기 연산을 마지막에 하기 때문에 위 코드와 같은 문제가 생기지 않는다..

    int f( int n, int k, int a = 1, int b = 1 ) {
        if ( k == 0 )
            return a / b;
        else
            return f( n - 1, k - 1, a * n, b * k );
    }

    a와 b에 계속 곱했다가 마지막에 나누는 방법인데... 값을 조금만 크게 줘도 오버플로우가 생긴다...


    이제 꼬리재귀가 제대로 적용되는지 확인해보자...

    bc.cpp(꼬리재귀X)랑 bc_tail.cpp(꼬리재귀O)를 만들어서 실험해봤다.. 둘다... -O2랑 -g 옵션 줘서... 컴파일함...

    bc.cpp

    bc_tail.cpp


    그냥 재귀로 된 건 이렇게 스택이 쌓이지만...


    꼬리재귀 함수는 main에서 반복문이 도는 형태로 바뀌었다. 그래서 스택이 계속 쌓이지 않는다...


    ㅜㅜ....


    추가: 아래와 같은 형태는 어떻게 꼬리재귀 형태로 바꿀 수 있을까?

    int f(int n, int k) {
        if (k == 0 || k == n)
            return 1;
        else
            return f(n-1, k-1) + f(n-1, k);
    }



    Posted by 코요

티스토리 툴바