[알고리즘/인프런정리] 1-3. Designing Recursion

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

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

- 모든 case는 결국 base case로 수렴해야 함

if ( ) {

  // base case;

}else {

  // recursion;

}

 

 

암시적 매개변수를 명시적 매개변수로 바꾸어라.

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

절차적

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

이 함수의 미션 : data[begin] ~ data[end] 사이의 target을 검색하는 것이다.

검색구간의 시작점을 명시적(explicit)으로 지정한다. => 명시적 매개변수

 

- 이 함수를 search(data, 0, n-1, target) 으로 호출한다면 절차적 방식과 완전히 동일한 일을 하는 것이다.

- 순환 형식으로 짤 경우, 함수 밖에서 호출될 때의 상황만 고려하는게 아니라 함수 내부에서 어떻게 쓰일지까지 고려하면서 매개변수를 지정해야 한다.

 => 시작점(begin) 명시적으로 표현해야 함

 

 

다른 버전 1 (거꾸로 탐색)

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

begin부터 탐색이 아니고, end부터 거꾸로 탐색을 한다.

 

 

다른 버전 2 (중간 탐색)

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

(binary search 와는 다름)

 

 

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

 

기본 버전

int findMax(int[] data, int begin, int end) {
	if(begin == end) // 시작과 끝이 같다면 갯수가 1개인 경우라 바로 리턴함. (0인 경우는 최대값이 있을 수 없음)
    	return data[begin];
    else
    	return Max.min(data[begin], findMax(data, begin+1, end)));
}

이 함수의 미션 : data[begin]~data[end] 사이 최대값 찾아서 반환. (begin <= end 라고 가정함)

 

다른 버전 (middle 값 사용)

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 (이진 검색)

- 작->큰 순서대로 정렬이 되어있다고 가정

- 가운데 위치를 middle로 둔다.

  찾는 값이 middle값 보다 작을 경우 -> begin ~ middle-1 사이 이진 검색

  찾는 값이 middle값 보다 클 경우 -> middle+1 ~ end 사이 이진 검색

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(itemsm, target, middle+1, end);
    }
}