순환(Recursion)에 대해(3)

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

순환 알고리즘의 성립 조건

- 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 꼭 있어야 한다. (base case는 여러 개가 있을 수 있다.)

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

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

- 순차 탐색 (데이터가 정렬되어 있다면 이진검색이 더 효율적이다.)

//이 함수의 임무는 data배열 내에서 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;

}

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

//위 예시와 같은 임무를 가지고 있으나 검색구간의 시작점을 begin 변수를 통해 명시적으로 지정한다는 차이점이 있다.

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

}

-> 이 함수를 search (data, 0, n - 1, target)으로 호출하게 되면 바로 앞의 함수와 완전히 같은 프로세스로 진행된다.

- 순차탐색의 다른 방법으로는 거꾸로 begin변수를 그대로 두고 end를 -1씩 하며 탐색을 할 수 있다.

- 순차 탐색 : middle변수 활용 (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) //중간값인 middle의 앞에서 target을 찾을 수 있다면 해당 인덱스를 리턴

return index;

else //중간값인 middle의 앞에 없다면 중간값 뒤부터 target을 찾아나간다.

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

}

}

-> 타겟과 중간값을 비교해 비교값이 음수면 타겟이  중간값보다 작다는 뜻이며 양수면 크다는 뜻이다. 이를 통해 반씩 범위를 줄여가며 최종적으로 찾고자 하는 값을 찾아나간다.