순환(Recursion)의 개념과 기본 예제 3

순환 알고리즘의 설계(Designing Recursion)

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

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

---

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

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

암시적 매개변수

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

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

 

명시화

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);
    // else return search(data, begin, end - 1, target);
}

- 검색 구간의 시작점을 명시적으로 지정한다.

 

명시화의 다른 버전

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);
    }
}

 

매개변수의 명시화 - 최댓값 찾기

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)

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);
    }
}