nCr 재귀함수의 호출횟수를 구해야 하는데 질문 좀 드려도 될까요..

nCr = n-1Cr + n-1Cr-1 을 이용하여 nCr을 구하는 재귀함수가 있습니다.

이렇게 생긴 앤데요 :

 1
2
3
4
5
6
7
8
9
10
 long long int choose2 (int n, int r)
{
 
    if(memo[n][r]>0) return memo[n][r];
    if(r==0 || n==r) return memo[n][r]=1;
    
    return memo[n][r] = choose2(n-1, r-1)+choose2(n-1,r);
}
 
Colored by Color Scripter
 cs

(보기만 해도 아시겠지만 memo는 값을 저장하기 위해 있는 배열입니다)

이때, nCr을 구하기 위해 저 choose2라는 함수를 호출하는 횟수를 n과 r에 대한 식으로 나타내야 합니다.

..도저히 감이 안 잡혀서 일단 노가다를 했는데요.

파스칼의 삼각형에 넣어보니 등차수열이 있는 걸 발견할 수 있었고, 호출횟수 역시 구할 수 있었습니다.

하지만 왜 저렇게 되는지 제 머리로는 이해가 되지 않습니다..ㅜㅜ 책에도 풀이가 없고.. 어떻게 검색해봐야 할지도 모르겠고.. 왜 저게 등차수열이 될까요??