순환적 알고리즘 설계
적어도 하나의 base case가 있어야한다.
모든 case는 결국 base case로 수렴해야 한다.
암시적 매겨변수를
명시적 매개변수로 바꾸어라
이 말이 무슨 뜻일까?
순차 탐색을 예로 들어보자.
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은 보통 생략한다. 즉 암시적 매개변수이다.
일반적으로 recursion을 사용하지 않는 함수에서는 이렇게 암시적으로 생략할 수 있다면
생략하는 것이 코드의 간결성 관점에서 좋다.
하지만 recursion 프로그래밍을 할때는 일반적으로 저렇게 하지 않는 것이 좋다.
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);
}
이 코드는 위의 코드를 recursive하게 변경한 코드이다.
배열 데이터가 있고 target의 인덱스를 찾고 싶다면
이전 코드에는 순서대로 검사 후 찾아내는 절차적 프로그래밍 이라면
첫번째 값이 타겟이라면 찾은것이고 그 경우는 첫번째 값의 인덱스를 리턴하고
아니라면 나머지 구간을 검색하면 된다.
두 코드의 차이는 검색할 구간의 명시이다.
두번째 코드는 시작위치 마저 명시되어있다. 이게 더좋은 이유는
다시 자기자신을 호출할때 다른 일을 하게 만들어야 하기때문에
그렇게 설계해야만 한다. 맨처음의 일만 생각하여 매개변수를 넣으면
안된다.
거꾸로 검색해도 같은 결과를 얻을 수 있다.
그때는 begin을 고정으로 두고 end값을 줄여가며 검색할 수 있다.
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);
}
}
순차 탐색의 다른 버전이다.
이진 탐색과는 다르다.
시작점과 끝점의 가운데 위치가 타겟이라면 리턴하고
아니라면 시작점과 중간점-1로 두고 검사한다.
매개변수의 명시화 : 최대값 찾기
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);
}
일반적으로 우리가 데이터들이 어떤 배열에 저장되어있을때
최대값을 찾을때의 함수의 매개변수는 일반적으로
findMax(int[] data, int n) 이렇게 설계한다.
recursion을 이용한다면 배열 데이터에 관심있는 데이터의 시작위치와 끝 위치의 매개변수가 필요하다.
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(comResult == 0)
return middle;
else if(compResult<0)
return binarySerach(items, target, begin, middle-1);
else
return binarySearch(items, target, middle+1 end);
}
}
이진 탐색이란 데이터들이 크기순으로 정렬되어있을때 적용할 수 있는 검색방법이다.
먼저 가운데 데이터를 비교하여 동일하다면 리턴하고
그보다 크다면 시작점을 중간점 이후로 이동한다.
그보다 작다면 종료점을 중간점 이전으로 이동한다.
이과정을 recursive하게 동작하면 된다.
이진 탐색은 그 자체로 recursive하다.
순환알고리즘을 설계하는데에 있어서 암시적 매개변수를 명시적 매개변수로 바꾸는 것이 중요하다.
