[고급-2] 재귀함수의 설계

학습 목표

-문제를 통해 수학적인 함수의 관계를 모색하고 이를 함수로 정의할 수 있다.

-다양한 패턴 출력 문제를 통해 수학적 귀납법을 적용할 수 있는 다양한 도메인을 학습할 수 있다.

-경우의 수를 세는 방법을 이해하고 수학적 접근과 정보과학적인 접근의 차이점을 이해할 수 있다.

1. 재귀함수 기초 3

<숫자 뒤집기>

하나의 정수를 거꾸로 출력하는 프로그램.

예)123

{첫번째 방법. 단순 출력} : 1등분

void f(int n){
    if(n==0) return;
    printf("%d", n%10);
    f(n/10);
}

{두번째 방법. 오른쪽 끝의 숫자*(자리수-1) 해서 저장.}(자리수는 으로 구한다. : 2등분

int f(int n){
    if(n<0) return n;
    return f(n/10)+(n%10)*powf(10.0,(int)log10((double)n);
}

{세번째 방법. 일의자릿수, 가장 큰 자릿수의 위치를 바꿔준다고 생각.} : 3등분

int f(int n){
    if(n<0) return n;
    return (n%10)*T*f((n%T)/10*10+n/T;//T==log n
}

<별 그리기>

N층의 삼각형 모양의 별을 출력.

{첫번째 방법. i행에 i개의 "*"이 n행에 걸쳐 그려진 별 패턴.}

void f(int n){
    if(n==1) printf("*\n");
    else{
        f(n-1);
        for(int i=0; i<n; ++i) printf("*");
        puts("");//==printf("\n");
    }
}

{두번째 방법. 배열에 현재 줄에 출력할 별을 미리 저장해둔다.}

char star[MAXN+1];
 
void f(int n){
    if(n>1){
        f(n-1);
        star[n]="*";
        puts(star+1);
    }
}

<경우의 수 : 조합(nCk)>

n개 중에서 k개를 고르는 경우의 수.

{첫번째 방법. f(n, k)=n개에서 k개를 고르는 경우의 수}

n=3, k=2라고 가정했을 때, (세 개의 칸에서) f(n, k) = 마지막 칸을 선택한 경우의 수 + 마지막 칸을 선택하지 않은 경우의 수

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

{두번째 방법. nCk의 수학식을 변형.}

f(n, k-1) = n! / { (k-1)! * (n-k+1)! }

=> f(n, k) = f(n, k-1) * { (n-k+1) / k }

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