2. Recursion(2)

인프런의 '영리한 프로그래밍을 위한 알고리즘 강좌' 내용 정리입니다.

        순환적 알고리즘의 설계

• 적어도 하나의 base case, 순환되지 않고 종료되는 case가 반드시 있어야한다.
• 모든 case는 결국 base case로 수렴해야함.
• 암시적 매개변수를 명시적 매개변수로 바꾸어라.

---

        다양한 예들

• 순차 탐색(sequential search) - recursion이 없는 버전

// data[0]에서 data[n-1] 사이에서 target을 검색하는 것.
// 검색 구간의 시작 인덱스 0은 보통 생략(암시적 매개변수)

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

• 암시적 매개변수, 명시적 매개변수 무슨 차이인가?
  위의 순차 탐색의 경우를 살펴보자.
  search 함수의 매개변수엔 int n이라는 매개변수가 있다. 그리고 이를 기반으로 data[n-1]까지 검색을 해본다는 것을 명시적으로 알 수 있는 것이다. 하지만 data[0, ... , n-1] 즉 data[0]부터 시작하여 검색해야한다는 것은 어디에도 명시되어있지 않다. 다만 인간이 암시적으로 0에서부터 시작하겠지라고 생각할 뿐이다.
  
  
• 매개변수를 명시화한 순차 탐색(sequential search)

// data[0] 에서 data[n-1]이 아닌 data[begin] 에서 data[end] 사이에서 target을 검색한다.
// 매개변수 int begin을 넣어줌으로써 매개변수를 명시화해준다.

int search(int [] data, int begin, int end, int target) {
    if ( begin > end ) // 검색한 target이 data에 없는 경우
        return -1;
    else if ( target == data[begin] ) // 검색한 target을 data[begin]에서 찾은 경우
        return begin;
    else
        return search(data, begin+1, end, target); // recursion
}

• 순차 탐색 : 다른 버전

// binary search 아님, 주의
int search(int [] data, int begin, int end, int target) {
    if( begin > end ) 
        return -1;
    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] 사이에서 최대값을 찾아 변환하기.

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[end] 사이에서 target을 검색한다.

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(items, target, begin, middle - 1);
        else
            return binarySearch(items, target, middle+1 , end);
    }
}