Week 1-2 : How to code Recursive function

<180329>

- 재귀함수 만들기

1) 함수를 잘 정의하고, 그 정의를 그대로 활용하기

2) 어떻게 쪼갤지 생각하기..

3) 언제까지??(재귀의 종료, 탈출조건)

4) 점화식을 알고 있다면 그대로 표현하기.

- 구현해보기.

1) Sum(n) : 1부터 n까지의 합을 구하는 함수.

int Sum(int n)
{
    if(n < 1) return 0;
    return n + Sum(n-1);
}

>> 1부터 n까지의 합은 1부터 n-1까지의 합에 n을 더하면 된다.

>> 1보다 작은 수가 들어오면 0을 리턴하면 될 것 같다.

2) evenSum(n) : 1부터 n까지의 수 중 짝수의 합 구하기.

int evenSum(int n)
{
    if(n < 1) return 0;
    if(n&1) n--;
    return n + evenSum(n-2);
}

>> n이 짝수인 경우, 1부터 n까지의 수 중 짝수의 합은 1부터 n-2까지의 수중 짝수의 합에 현재 값을 더하면 된다.

>> n이 홀수일 수도 있으므로, 4번 라인에서 예외처리를 한번 더 한다.

>> 홀수의 경우 마지막 비트는 항상 1이다. 그러므로 홀수와 1을 비트연산을 하면 1이 나온다. 조건식에서 1은 참..!!

3) combi(n, r) : n개의 수 중 r개의 수를 뽑는 방법의 수.

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

>> 우리는 nCr = n-1Cr + n-1Cr-1 이라는 점화식을 알고있다....ㅎㅎ

>> 해당 점화식을 그대로 표현했을 뿐이다. 

>> 즉, n개의 수 중 r개의 수를 뽑는 방법의 수는 

     임의의 수 하나를 무조건 뽑는 다고 생각했을 때인, n-1개의 수 중 r-1 개를 뽑는 방법에 수와 

     그 임의의 수 하나를 무조건 안뽑는다고 생각햇을 때인, n-1개의 수 중 r 개를 뽑는 방법에 수를 더하면 된다.

>> 그리고 우리는 nC0 == nCn == 1 이라는 것을 알고 있다. 그대로 탈출조건에 적용하면 된다.

4) print1(n) : 1부터 n까지 출력하는 함수

void print1(int n)
{
    if(n < 1) return ;
    print1(n-1);
    printf("%d\n", n);
}

>> 1부터 n까지 출력하는 것은 1부터 n-1까지 출력한 다음에 n만 출력하는 것과 같다.

5) print2(n) : n부터 1까지 거꾸로 출력하는 함수.

void print2(int n)
{
    if(n < 1) return ;
    printf("%d\n", n);
    print1(n-1);
}

>> n부터 1까지 거꾸려 출력하는 것은 n을 먼저 출력하고 n-1부터 1까지 거꾸로 출력하는 것과 같다.

6) arrSum(int arr[], int n) : 배열 arr에서 0번째 값에서 n번째 값까지의 합을 구하는 함수.

int arrSum(int arr[], int n)
{
    if(n == 0) return arr[0];
    return a[n] + arrSum(arr, n-1);
}

>> 배열 arr에서 0값 요소에서 n번째 값까지의 합은 배열 arr에서 0번째 값에서 n-1번째 값까지의 합에 n번째 값을 더하면 된다.

7) arrMax(int arr[], int n) :  배열 arr에서 0번째 값에서 n번째까지의 값 중 최대값을 구하는 함수

int arrMax(int arr[], int n)
{
    int k;
    if(n == 0) return arr[0];
    k = arrMax(arr, n-1);    
    return a[n] > k ? a[n] : k;
}

>>  배열 arr에서 0번째 값에서 n-1번째까지의 값 중 최대값이 k라고 하자.

      then, k와 a[n] 중에서의 최대값이 배열 arr에서 0번째 값에서 n번째까지의 값 중에서 최대값이 된다.

>> 시각적인 이미지 참고 블로그(전에 설명 들은 동생이 정리해놨다..ㅎㅎ) : http://mattlee.tistory.com/17?category=680710

- 숙제 : 배열의 값들 중 두번째 최대값 구하기.