Designing Recursion | 순환 알고리즘의 설계
[기본]
(1) 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case 가 있어야 한다.
(2) 모든 case 는 결국 base case 로 수렴해야 한다.
암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꿔라
[순차 탐색]
이 함수의 미션은 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;
}
Java
복사
만약 recursion 으로 이 함수를 바꾼다면 검색구간의 시작점을 명시적(explicit) 으로 지정해야 한다.
| 순차 탐색 순환버전 1
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);
}
Java
복사
만약 이 함수를 search(data, 0, n-1, target) 으로 호출 한다면 첫번째 함수(암시적 매개변수 예제) 와 완전히 동일한 일을 한다.| 순차 탐색 순환버전 2
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);
}
Java
복사
| 순차 탐색 순환버전 3
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);
}
}
Java
복사
binary search 가 아니다. [최대값 찾기]
이 함수의 미션은 data[begin] 에서 data[end] 사이에서 최대값을 찾아 반환한다. begin ≤ end 라고 가정한다.
| 버전 1
int findMax(int[] data, int begin, int end) {
// data 개수가 하나일 때를 base case 로 가진다.
if (begin == end)
return data[begin];
else
return Math.max(data[begin], findMax(data, begin+1, end));
}
Java
복사
| 버전 2
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);
}
}
Java
복사
[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 if (compResult > 0)
return binarySearch (items, target, middle + 1, end);
}
}
}
Java
복사