재귀함수로 조합 구현하기

#include <stdio.h>

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

int main(void)
{
int n, r;
char c;
scanf("%d%c%d", &n, &c, &r);
printf("%d", nCr(n, r));
return 0;
}

 

코드 해석

 

int nCr(int n, int r) == nCr이라는 함수를 정의하고 매개변수로 n,r을 정의한다

--------------------------------------------------------------------------------------------

if(r == 0 || r == n)
{
return 1;
}

== r이 0이거나 n이면 1을 반환한다

--------------------------------------------------------------------------------------------

else
{
return nCr(n-1, r-1) + nCr(n-1, r);
}

== 이외의 경우 nCr(n-1, r-1)과 nCr(n-1,r)을 더한 값을 반환한다

--------------------------------------------------------------------------------------------

int n, r; == n, r 선언

char c; == 문자형 c 선언

scanf("%d%c%d", &n, &c, &r); == n, c, r 순서로 값을 입력

printf("%d", nCr(n, r)); == 입력받은 n,r 값으로 계산된 nCr 출력

 

 

내가 생각한 중요포인트

: nCr = nCr(n-1, r-1) + nCr(n-1,r)처럼 나타낸 식은 프로그래밍으로 표현하기 쉽다

3C1같은 경우 r이 0도 아니고 n도 아니기 때문에 else로 가서 2C0 + 2C1을 반환한다

그리고 2C0은 r이 0이기 때문에 1로 반환되고 2C1은 또 1C0 + 1C1로 반환된다

1C0은 1로 반환되고 1C1도 1로 반환되기 때문에 답은 3

 

 

 

 

 

 

 

(틀린 사항이 있다면 지적부탁드립니다)