C - 재귀함수

재귀함수란 ? 

함수 스스로가 자기자신을 호출하는 함수를 칭한다.

재귀함수의 특징으로 자기자신을 호출할 때마다 사용되는 변수들이 스택에 보관되며 return문이 실행 될 때마다 스택에서 복원하여 사용한다.

 

void hello(int count) {
    if(count == 0) {
        return;
    }
     printf("Hello~ %d \n", count);
     hello(--count);
}
int main() {
    hello(10);

    return 0;
}

출력 결과

Hello~ 10 
Hello~ 9 
Hello~ 8 
Hello~ 7 
Hello~ 6 
Hello~ 5 
Hello~ 4 
Hello~ 3 
Hello~ 2 
Hello~ 1

위 예시와 같이 종료조건을 꼭 설정해주도록 하자!

 

특정 값을 입력 받아 문자열을 반복하는 재귀 함수

void print(int count){
    if(count == 0){
        return;
    }
    else{
        printf("문자열을 출력합니다\n");
        print(count-1);
    }
}
int main() {
    printf("문자열을 몇개 출력할까");
    int number;
    scanf("%d", &number);
    print(number);
}

출력 결과

문자열을 몇개 출력할까7
문자열을 출력합니다
문자열을 출력합니다
문자열을 출력합니다
문자열을 출력합니다
문자열을 출력합니다
문자열을 출력합니다
문자열을 출력합니다

 

고등학교 확률과 통계시간에 배운 조합을 재귀함수로 간단히 표현할 수 있다.

//재귀함수로 조합 구현하기
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() {
    int n, r;
    scanf("%d %d",&n, &r);
    printf("%d", nCr(n,r));
}

출력 결과

10
5
252