순환(Recursion)의 개념, 기본예제3

순환적 알고리즘 설계

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

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

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

순차 탐색

int search(int [] data, int n, int targer){
  for(int i = 0; i<n; i++)
    if(data[i]==target)
      return i;
  return -1;   // 찾고 있는 값이 없음.
}

=> 이 함수의 미션은 data[0]에서 data[n-1] 사이에서 target을 검색하는 것이다. 하지만 검색 구간의 시작 인덱스 0은 보통 생략한다. 즉 암시적 매개변수이다.

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

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

int sertch(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)으로 호출한다면 앞 페이지의 함수와 완전히 동일한 일을 한다.

recursion의 형태를 가지는 함수는 외부에서 호출될때만 생각해서 암시적 매개변수로 설계하는 것보다 매개변수를 명시화해서 일반적인 형태로 설계하는 것을 지향한다. 

순차 탐색: 다른 버전 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[end])
    return end;
  else
    return search(data, begin, end-1, target);
}

순차 탐색: 다른 버전 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와는 다름.

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

data[begin]에서 data[end] 사이에서 최대값을 찾아 반환한다. begin<=end라고 가정한다.

int findMax(int [] data, int begin, int end){ /* int begin, int end 명시적 매개변수 */
  if(begin==end) // 값이 하나이다! 하나의 값이 최대값이면서 최대값이 된다.
    return data[begin];
  else // 그렇지 않은 경우, 첫번째 값을 제외한 나머지 값을 recursion으로 구한 후 첫번째 값과 비교한다!
    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); // 끝점에서 중간점+1까지의 범위에서 최대값을 찾는다.
    return Math.max(max1, max2); 
}

Binary Search(이진 검색)

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

Reference

• 인프런, "영리한 프로그래밍을 위한 알고리즘 강좌, 제1-3강 Recursion의 개념과 기본 예제들(3/3)", https://www.inflearn.com/course/%EC%95%8C%EA%B3%A0%EB%A6%AC%EC%A6%98-%EA%B0%95%EC%A2%8C/lecture/4074(2020.04.21)