Binomial Coefficient (recursive)

1. Problem

- nCk를 계산해보자.

 

2. Input

1) 음이 아닌 정수 n

2) 음이 아닌 정수 k

- 이때 k <= n

 

3. Output

1) nCk의 값

- C는 수학에서 조합을 나타내는 기호로, nCk는 n!/(k!(n-k)!)으로 계산된다.

 

4. PseudoCode

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

 

5. Example

class AlgoTest {
    public static void main(String[] args){
        System.out.println(bin(5,3)); // 10
    }
    
    static long bin(int n, int k) {
        if(k==0 || n==k)
            return 1;
        else
            return bin(n-1, k-1) + bin(n-1, k);
    }
}

- T(n) = 2^n -1