[알고리즘] Recursion 이란 - 3

Recursion(재귀) 이란 - 3

암시적 매개 변수의 명시적 표현

앞에서 배운 Recursion의 내용을 다시 한번 종합해보자면 다음과 같다.

1. 적어도 하나의 base case를 가지고 있어야한다, 

즉 순환되지 않고 종료되는 case가 있어야한다.

2. 모든 case는 base case로 수렴해야한다.

여기서 추가적으로 코드를 작성하는 방법으로는,

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

예제를 살펴보자

순차탐색

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은 보통 생략한다.

즉 시작 인덱스 0은 암시적 매개변수이다.

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

첫번째 예제를 재귀로 표현한 코드이다.

앞서 말한것 처럼 암시적 매개변수를 명시적으로 변환해준다.

즉, 시작 인덱스 0을 begin으로 명시적으로 표기해준다.

따라서 이 함수는 data[begin]에서 data[end] 사이에 target을 검색한다.

이 함수를 search(data, 0, end, target)으로 호출한다면

첫번째 예제와 동일하게 동작한다.

이렇게 명시적으로 매개 변수를 변환하는 이유는 무엇일까

일반적으로 재귀 함수의 형태를 가지는 함수의 매개변수들은 

처음 이 함수가 외부에서 호출될 때의 상황만 고려하여 설계해서는 안된다

 함수가 다시 자신을 재귀로 호출할 때 필요한 매개변수들까지 표현할 수 있는 

일반적인 형태를 가져야 하기 때문이다.

즉, 매개 변수를 명시적으로 지정해주지 않으면 재귀 호출 시 시작구간이 달라지므로

그것을 표현할 방법이 없어지기 때문이다.

때문에 재귀함수에서는 매개변수를 최대한 명시적으로 표현하는것이

우리가 재귀적으로 함수를 작성하는데 수월해진다.

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, 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);
    }
}
 

다음은 순차 검색을 좀더 확장한 예제이다.

가운뎃 값을 기준으로 앞뒤로 탐색하여 탐색시간을 줄였다.

가운뎃 값은 begin과 end가 명시적으로 표시되었으므로 사용이 가능하다.

배열의 최대값 찾기

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

최대값 찾기의 다른 버전이다.

순차 탐색의 심화 버전과 마찬가지로 가운뎃 값을 설정한다.

가운뎃 값을 기준으로 왼쪽, 오른쪽의 재귀 함수의 결과를 비교한다.

이진 검색

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

이진 검색 코드이다.

이진검색은 기본적으로 데이터가 정렬되었다는 가정하에 진행된다.

중간 값을 나누어서 target과 중간 값을 비교한다.

값이 같다면 해당 값을 리턴해주고

target이 크다면 왼쪽을, 작다면 오른쪽으로 재귀함수를 호출한다.

이진 검색의 알고리즘은 사전에서 단어를 찾을때와 비슷하다고 생각하면 된다.

결론적으로 재귀 함수를 동작시킬때 가능한 

암시적 매개 변수가 아닌 명시적 매개 변수로 표현해야한다는 것이다. 

 

출처 : 부경대 권오흠 교수님, 영리한 프로그래밍을 위한 알고리즘