재귀함수 개념, 문제

1. 재귀함수(Recursive Function)

재귀의 조건 생각하기 -->탈출조건, 끝나는 메커니즘

재귀함수의 정의를 이용해서 함수의 이름을 만들고, 그 정의를 재귀적으로 사용한다.

원하는 결과를 얻기 위해서 과정을 쪼개서 생각한다. 초기 설정만 잘 해주면 컴퓨터가 알아서 계산해준다.

반환형을 생각한다.

2. Factorial : 1~n까지의 곱을 재귀함수로 구하기.

     

#include <stdio.h>
 
int factorial(int n) {
    if (n == 0)
        return 1;
    
    else 
        return n*factorial(n - 1);
}
 
int main(void) {
 
    int n;
    scanf("%d", &n);
 
    printf("%d\n", factorial(n));
 
    return 0;
}

1. 1~n의 곱을 어떻게 쪼개서 생각할 것인가? : n*(n-1)!으로 생각한다.

2. 재귀함수 종료(탈출조건) : Factorial함수는 n==0일때 종료.(단, 0! = 1)

3. 함수 Factorial은 n과 (n-1)!을 곱하는 함수이다. 그리고 n==0일때 종료된다.

3.1 0~n까지 printf를 재귀함수로 하기.(내림차순)

#include <stdio.h>
 
void printNumber(int n) {
 
    if (n == -1)
        return;
    else {
        printf("%d\n", n);
        printNumber(n - 1);
    }
}
 
 
int main(void) {
 
    int n;
    scanf("%d", &n);
 
    printNumber(n);
 
    return 0;
}
 

1. 0~n을 print하기 위해서 어떻게 쪼개서 생각할 것인가? : n을찍고 n-1부터 0까지는 재귀함수가 알아서 한다고 생각한다.

2. 재귀함수의 탈출조건 : 0까지 찍고, n의 값이 -1이 되면 return.

3. 함수 PrintNumber은 n을 찍고, PrintNumber(n-1)을 실행하는 함수이다. 그리고 n==-1일떄 종료된다.

3.2 n~0까지 printf를 재귀함수로 하기.(오름차순)

#include <stdio.h>
 
void printNumber(int n) {
 
    if (n == -1)
        return;
    else {
        printNumber(n - 1);
        printf("%d\n", n);
        //printNumber(n - 1);
    }
}
 
 
int main(void) {
 
    int n;
    scanf("%d", &n);
 
    printNumber(n);
 
    return 0;
}

먼저 찍고 재귀를 할 것인가? 재귀를 끝까지 돌리고 찍을 것인가?

함수에 조금씩 다른 의미를 준다.

4. paildrome(회문) : 회문의 여부를 재귀함수로 판단하기.

#include <stdio.h>
#include <string.h>
 
#define MAX_STR 100
 
void paildrome(char str[], int i, int j) {
    if (i >= j) {
        printf("Paildrome!\n");
        return;
    }
 
    else {
        if (str[i] != str[j]) {
            printf("Not paildrome\n");
            return;
        }
        paildrome(str, i + 1, j - 1);
    }
 
}
 
int main(void) {
 
    char str[MAX_STR];
    scanf("%s", str);
 
    paildrome(str, 0, strlen(str) - 1);
 
    return 0;
}

 

1. 회문판단함수 설계 : 처음 배열 index와 마지막 배열 index가 서로 같은지 확인, 그 이후로 i++,j--를 하면서, 모든 요소 확인

컴퓨터가 알아서 해준다고 생각한다.

2. 재귀함수의 탈출조건 : 처음에 설정한 i(맨 처음부터 그 뒤의 index를 가리킨다.), NULL의 다음을 가리킨 j를 비교한다. 나중에는

      i>=j가 되는 상태까지 가는데, 이것이 탈출조건이다.

3. 서로 짝지어서 확인하고 탈출조건까지 확인이 된다면, 회문이다. 중간에 두개의 문자가 서로 다르다면 회문이 아니다.

5. 배열에 있는 가장 큰 수를 찾기.

#include <stdio.h>
 
#define ARR_NUM 5
 
int findMaxNum(int* arr, int n) {
    int k;
 
    if (n == 0) return arr[0];
 
    k = findMaxNum(arr, n - 1);
 
    return k > arr[n] ? k : arr[n];
 
}
 
int main(void) {
 
    int arr[ARR_NUM] = { 0 };
    int max;
    for (int i = 0; i < ARR_NUM; ++i) {
        scanf("%d", &arr[i]);
    }
 
    max = findMaxNum(arr, ARR_NUM);
 
    printf("%d\n", max);
    
 
    return 0;
}

1. 1~n-1중에서 가장 큰 수와 arr[n]을 비교한다.

2. 조건식에 부합하다면, 1~n-1사이에 가장 큰 수가 있는 것이다.

3. 1~n-1, n을 비교한다. 그러면 나머지는 컴퓨터가 설계한다.(사실 모든 연산은 컴퓨터가 하는것이지만, 초기 설계의 입장에서.)

6. 홀수의 합을 재귀함수로 구하기.

#include <stdio.h>
 
int oddSumByRecur(int num) {
    if (num < 0) return 0;
 
    int total = 0;
 
    if (num % 2 == 0) {
        num = num - 1;
    }
    
    return total = num + oddSumByRecur(num - 2);
 
}
 
int main(void) {
    int num;
    int total = 0;
 
    scanf("%d", &num);
 
    total = oddSumByRecur(num);
 
    printf("%d\n", total);
 
    return 0;
}

1. 함수 설계 : 함수를 정의한다. 1부터 num까지의 홀수의 합을 구하는 것으로.

2. 탈출 조건 설계 : num의 값이 0보다 작으면, 그 함수를 종료시킨다.

3. 처음 들어온 값이 홀수, 짝수에 따라서 약간 달라진다.

7. PrintComma : 주어진 값을 1000의 자리마다 Comma를 찍기.

#include <stdio.h>
 
void PrintComma(int n) {
    int temp = n / 1000;
 
    if (temp > 0) {
        PrintComma(n / 1000);
        printf(",%.03d", n % 1000);//3자리확보, 빈자리면 0
    }
 
    else {
        printf("%d", n);
        return;
    }
}
 
int main(void) {
 
    int n;
    scanf("%d", &n);
 
    PrintComma(n);
 
    return 0;
}
 

1. 함수 설계 :세 자리마다 comma를 찍어주어야 한다. 그래서 1000을 나눌 생각을 한다. 

2. 탈출 조건 설계 : 나눈 값이 <0이라는 것은, 결국 세 자리 단위로 자를 수 없다는 것, 그러므로 그냥 프린트하고 return한다.

3. 8번째 줄은 약간의 테크닉이 필요한데, 3개의 자리를 우선 할당한 다음, 만약 그 자리가 빈자리라면 0을 출력한다는 의미이다.

4. 재귀함수의 모든 과정을 생각하면 안된다. 단순히 초기식만 잘 잡으면 알아서 컴퓨터가 해준다고 생각하자.