알고리즘: 재귀함수 (2) Designing Recursion

설계 조건

1. 적어도 하나의 Base Case가 존재해야 함. ( 종료되는 case )
2. 모든 case는 결국 Base Case로 수렴함.

Recursion과 반복문 작성시 주목할 차이점

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

예시 (1)  순차 탐색 [ Sequention Search ]

 

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

 

• 말 그대로 순차적으로 탐색하는 알고리즘으로 찾는 데이터가 어디에 위치하는지 index 번호 리턴하는 경우
• 만약 데이터가 정렬되어 있다면 이진검색 진행
• 만약 순차 검색을 위와 같이 설계한다면
  검색 구간은 index[0] ~ index[n - 1] 구간을 검색하는 것임. 이때 n-1은 명시적으로 표현되어 있으나, index[0]은 묵시적으로 시작 값이라는 것을 알기에 이는 암시적 매개변수임.
• 즉, 시작지점이 따로 명시되어 있지 않고 0부터 순환할 경우 이는 '암시적 매개변수'라고 볼 수 있음.
• 일반적으로 Recursion으로 사용하지 않는 경우에 위와 같이 사용함. 하지만 Recursion으로 프로그래밍을 할 때에는 명시화 함.

 

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

 

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

 

• Recursion
  원래 배열 데이터와 상관 없이 시작 값과 끝 값 사이에 값이 존재하는지 확인하는 것
• 기존 코드와 차이는 시작 값과 끝 값을 명시적으로 표현함.
• 이는 Recursion으로 작성할 때 염두해야하는 가장 기본적인 원칙임.
• 다시 자기 자신을 호출하며 시작 값은 변경됨.
  고로 일반적으로 Recursion으로 선언된 함수들은 매개변수들은 맨 처음 외부에서 호출 될 때의 상황만 생각하고 설계해서는 안 됨.
  무한루프에 빠질 수 있기 때문임.

 

순차 탐색 : 다른 버전

 

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

 

• begin 부터가 아닌 end부터 -1을 하며 begin까지 값을 탐색하는 것

 

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

 

    private int searchMax(int []data, int begin, int end){
        // begin이 마지막 번호까지 왔을 경우 배열의 마지막 데이터 반환
        if (begin == end) return data[begin];
        else {
            return Math.max(data[begin], searchMax(data, begin++, end));
        }
    }

 

• begin과 end 사이의 최대값을 찾음
• 이는 첫 번째 중에 제외한 최대값과 범위의 최대값과 비교해 가장 큰 값을 찾는 것임

매개변수의 명시화 : Binary Search

 

   private int binarySearch(String []items, String target,
                             int begin, int end){
                             
        // begin은 메서드가 실행하면 하나씩 증가함
        // 만약 증가하다 end보다 커질 경우 -1을 반환함
        if (begin > end) return -1;
        else{

            // 이진탐색법은 가운데 값을 기준으로 진행함
            int mid = (begin + end) / 2;
            /*

                compareTo는 비교하는 문자열과 각각의 자리를 비교해
                비교 값에서 매개변수의 값을 뺄셈하여 차이를 int형으로 반환함

                tmpStr.compareTo(str); 메소드
                만약 tmpStr이 str과 같으면 0,
                만약 tmpStr이 str 보다 크면 1,
                만약 tmpStr이 str 보다 작으면 -1

             */
            if ( items[mid].compareTo(target) == 0 ) return mid;
            else if ( items[mid].compareTo(target) > 0)
                return binarySearch(items, target, mid+1, end);
            else {
                // items[mid].compareTo(target) < 0
                // 즉, items[mid]의 값이 target 보다 작을 경우
                return binarySearch(items, target, begin, mid-1);
            }

        }

    }

 

참고. Binary search는 정렬된 데이터에 적용 가능