알고리즘 - 순환(Recursion)의 개념과 기본 예제 3

알고리즘 - 순환(Recursion)의 개념과 기본 예제 3

| 시작하기에 앞서,

순환적 알고리즘 설계

• 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 함.
• 모든 case는 결국 base case로 수렴해야 함.

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

| 순차 탐색

이 함수의 미션은 data[0]에서 data[n-1] 사이에서 target을 검색하는 것이다. 하지만 검색 구간의 시작 인덱스 0은 보통 생략한다. 즉 암시적 매개변수이다. (함수상에 0이라는값이 명시되어 있지 않다.)

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

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

이 함수의 미션은 data[begin]에서 data[end] 사이에서 target을 검색한다. 즉, 검색구간의 시작점을 명시적으로 지정한다.

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

이 함수를 search(data, 0, n-1, target)으로 호출한다면 앞 페이지의 함수와 완전히 동일한 일을 한다.
|  순차 탐색: 다른 버전
이 함수의 미션은 data[begin]에서 data[end] 사이에서 target을 검색한다. 즉, 검색구간의 시작점을 명시적(explicit)으로 지정한다.

int search(int [] data,int begin, int end, int target){
 if (begin>end)
   return -1;
  else if (target==items[end])
    return end;
  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);
  }
}

binary search 와는 다름.
| 매개변수의 명시화: 최대값 찾기

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

• 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
      return binarySearch(items, target, middle+1,end);
  }
}

순환함수의 기본은 명시적인 매개변수!