[ 개념 ] 19. 재귀(Recursion)의 기본 개념과 예제3

> Recursion의 기본 개념과 예제3

---

Desigining Recursion

순환적 알고리즘의 설계

• 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 한다

• 모든 case는 결국 base case로 수렴해야 한다

  ex - 가장 단순한 경우

  if(...){
      // basecase
  } else {
      // recursion
  }

• 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라!!

순차탐색

이 함수의 미션은 data[0]에서 data[n-1]사이에서 target을 검색하는 것이다. 하지만 검색 구간의 시작 인덱스 0은 보통 생략한다. 즉, 0은 암시적 매개변수이다.

int search(int[] data, int n, int target){
    for(int i=0; i<n; i++){
        if(data[i] == target)
            return i;
    }
    return -1;
}

매개변수의 명시화 : 순차탐색

• 이 함수의 미션은 data[begin]에서 data[end]사이에서 target을 검색한다. 즉, 검색구간의 시작점을 명시적으로(explicit)으로 지정한다.
• 이 함수를 `search(data, 0, n-1, target)으로 호출한다면 위에있는 순차탐색 함수와 완전히 동일한 일을 한다.

int search(int[] data, int begin, int end, int target){
    if(begin > end)
        return -1;
    else if (target == data[begin])
        return begin;
    else
        return search(data, begin+1, end, target);
}

순차탐색 : 다른버전

• 이 함수의 미션은 data[begin]에서 data[end] 사이에서 target을 검색한다. 즉, 검색구간의 시작점을 명시적으로 지정한다.

int search(int[] data, int begin, int end, int target){
    if(begin > end)
        return -1;
    else if (target == data[begin])
        return begin;
    else
        return search(data, begin, end-1, target);
}

순차탐색 : 다른버전2

• Binary Search 와는 다르다.

int search(int[] data, int begin, int end, int target){
    if (begin > end)
        begin 01;
    else {
        int middle = (begin + end) / 2;
        if (data[middle] == target)
            return middle;
        int index = search(data, begin, middle-1, target);
        if (index != -1)
            return index;
        else
            return search(data, middle+1, end, target);
    }
}

매개변수의 명시화 : 최대값 찾기

• 이 함수의 미션은 data[begin]에서 data[end] 사이에서 최대값을 찾아 반환한다. begin <= end라고 가정한다.
• 여기서 최대값을 찾는 법은 첫번째 인덱스에 해당하는 값과, 첫번째 인덱스를 제외한 나머지 범위에서의 값을 비교한 것들중에 순환적으로 최대값을 찾는다.
• Base case 는 begin == end, 즉 데이터의 갯수가 1개인 경우다

int findMax(int[] data, int begin, int end){
    if (begin == end)
        return data[begin];
    else
        return Math.max(data[begin], findMax(data, begin+1, end));
}

최대값 찾기 : 다른버전

int findMax(int[] data, int begin, int end){
    if (begin == end)
        return data[begin];
    else {
        int middle = (begin + end) / 2;
        int max1 = findMax(data, begin, middle);
        int max2 = findMax(data, middle+1, end);
        return Math.max(max1, max2);
    }
}

Binary Search

• items[begin]에서 items[add] 사이에서 target을 검색한다.
• 해당 메소드에 매개변수를 명시적으로 표시하지 않는다면, recursion으로 구현할 떄 내부에서 recursive하게 호출되는 함수를 표현할 수 있는 방법이 없어진다.

public static int binarySearch(String[] items, String target, int begin, int end){
    if (begin > end)
        return -1;
    else {
        int middle = (begin + end) / 2;
        int compResult = target.compareTo(items[middle]);
        if (compResult == 0)
            return middle;
        else if (compResult < 0)
            return binarySearch(item, target, begin, middle -1);
        else
            return binarySearch(item, target, middle-1, end);
    }
}

따라서, 순환 알고리즘을 설계하는데에 있어서 가장 중요한 것은

• 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 함
• 모든 case는 결국 base case로 수렴해야 함
• 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라!