[JAVA] Recursion 설계

이번 포스팅에서는 이전 포스팅에서 다룬 Recursion 알고리즘을 설계하는 방법에 대해 알아보겠습니다.

순환적 알고리즘을 설계하는 조건 중 가장 중요한 것은 바로 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 한다는 것입니다. 그리고 모든 case가 결국 base case로 수렴하여 무한 반복을 탈출할 수 있어야 합니다.

 

---

1. 순차 탐색 Sequential  search

    public int search(int[] data, int n, int target){
        for(int i=0; i<n; i++){
            if(data[i]==target)
                return i;
        }
        return -1;	// 배열에 target과 매칭되는 값이 없음
    }

target 데이터와 매칭 되는 값이 배열에 존재하면 그 인덱스를 리턴하는 구조

함수의 매개변수 중 끝 지점이 n은 명시적(explicit) 매개변수이지만, 검색 구간의 시작 인덱스 0은 보통 생략하는데 이런 것들을 암시적(implicit) 매개변수라고 합니다.

---

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

같은 기능을 하는 함수라도 순환 함수를 사용하면 시작 구간을 매개변수를 통해 명시적으로 전달하고, 함수 내에서는 시작 구간의 위치를 한 칸씩 앞으로 이동시키며 순차적으로 탐색하는 방법입니다.

Recursion을 사용하는 함수의 매개변수는 함수 내에서 자기 자신을 다시 호출하는 상황까지 고려하여 설정해야 합니다.

---

위와 같이 middle로부터 범위를 둘로 나눠서 순차적으로 탐색을 하는 방법도 존재합니다.

---

여기서 findMax 함수의 토대가 되는 아이디어는

맨 처음 배열의 값(data[begin])과 그 뒤의 값들에서 가장 큰 값 중 큰 값이 배열에서 가장 큰 값이다

라는 아이디어입니다.

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

최대값 찾기 함수 역시 middle을 통해 범위를 둘로 나눠 두 범위 중 가장 큰 값이 배열에서 가장 큰 값이라는 아이디어를 사용할 수 있습니다.

---

이번에는 이진 검색(Binary Search)에 대해 알아보겠습니다. 이진 검색은 기본적으로 배열이 순서대로 정렬되어 있다는 전제에서 시작합니다. 단어 검색을 예로 들면, 단어가 저장된 배열이 알파벳 순으로 정렬되어있고 찾으려는 단어와 배열에 저장된 단어의 첫 번째 글자가 가리키는 아스키 값을 통해 찾아냅니다.

String 자료형의 compareTo 함수는 자기 자신과 매개변수로 받는 문자열을 비교하는데, 두 값이 같다면 0을 출력, 자신이 더 작으면 음수를, 반대로 자신이 더 크다면 양수를 리턴합니다.

때문에 두 단어를 같다면 middle을 리턴하고,

target보다 items [middle]의 값이 더 큰 경우, 즉 단어의 순서가 target이 더 앞 단일 때에는 다시 binarySearch 함수를 호출해서 범위를 begin부터 middle-1로 명시적으로 전달해줍니다.

target보다 items[middle]이 더 작은 경우엔 이와 반대로 middle+1부터 end 사이에서 다시 이진 검색으로 답을 찾습니다.

binary search는 특히 시작 범위와 종료 범위를 암시적 매개변수로 정하면 그 구현이 까다롭기 때문에 위의 예제처럼 명시적 매개변수를 정하는 것이 중요합니다.