8. Recursion -3 (Java)

Goal

 - Designing Recursion 순환 알고리즘의 설계

 - 암시적 매개변수를 명시적 매개변수로 

 - 암시적 매개변수를 이용한 recursion코드 예제

1. Designing Recursion 순환 알고리즘의 설계

 - 무한 루프를 피하기 위한 2가지 조건 

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

 - 2) 모든 case는 결국 base case로 수렴해야 함 

 - recursion인 함수와 아닌 함수를 작성할 때의 차이 

  -> recursion 함수에는 암시적 (implicit) 매개변수가 없음

 

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

 - 보통 함수를 만들 때 반복문을 사용하면, 끝값은 index n-1, 시작값은 0이다. 이는 끝값은 명시하지만 시작값은 암묵적으로 0으로 사용한다는 것을 동의하는 것으로 이를 암시적 매개변수를 사용한다라고 함. 

 - recursion을 만들 때는 암시적 매개변수를 사용하지 않고, 명시적 매개변수를 사용한다. 즉 시작값과 끝값을 명시한다.

 

예제 1) 보통의 함수에서 순차탐색 구현

 - 이 함수는 data[0] 에서 data[n-1] 까지 확인하며 target을 탐색한다.

 - 시작값을 매개변수로 주지 않고 반복문을 통해 0부터 탐색한다.

 - 이는 보통의 함수를 만들때 사용하는 보편적인 방법으로 검색 구간의 시작 인덱스 0은 보통 생략한다. 즉, 암시적 매개변수를 사용한다.

 

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

 

예제 2) recursion을 통한 순차탐색 구현 : 매개변수의 명시화 

 - data[begin]에서 data[end] 까지 검색하며 target을 찾음.

 - 즉, 검색구간의 시작점을 매개변수로 선언하여 시작값을 명시적으로 지정함.

 - 이 함수를 seach(data, 0 , n - 1, target)으로 호출하면 암시적 순차탐색과 동일한 수행을 함.

 

    // 매개변수 명시화 순차탐색
    int search(int[] data, int begin, int end, int target) {
        if (begin > end) { //시작점을 명시함으로써 base case 생성 
            return -1;
        }
        else if (target == data[begin]) {
            return begin;
        }
        else {
            return search(data, begin + 1, end, target); // recursive case
        }
            
    }

예제 3) 순차탐색 : 다른버전 

 - end값 부터 -1을 하면서 순차적으로 target 탐색

    // 순차 탐색 : 다른버전
    int seach(int[] data, int begin, int end, int target) {
        if (begin > end) {
            return -1;
        }
        else if (target == data[end]) {
            return end;
        }
        else {
            return search(data, begin, end - 1, target);
        }
    }

 

예제 4) 순차탐색 : 다른버전2

 - binary search와는 다름

 - middle을 비교하고, 왼쪽으로 0인덱스까지 탐색 후, 0부터 data.length - 1까지 탐색하며 target을 찾는 함수. 

    int search2(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 = search2(data, begin, middle-1, target);
            if (index != -1) {
                return index;
            }
            else {
                return search2(data, middle + 1, end, target);
            }
        }
    }

 

예제 5) 매개변수의 명시화 : 최대값 찾기

 - Math.max(n1, n2) : 두 인자 값중 큰 값 리턴

    // 최대값 찾기
    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));
        }
    }

 

예제 6) 최대값 찾기 2

 

    // 최대값 찾기 2
    int findMax2(int[] data, int begin, int end) {
        if (begin == end) {
            return data[begin];
        }
        else {
            int middle = (begin + end) / 2;
            int max1 = findMax2(data, begin, middle);
            int max2 = findMax2(data, middle + 1, end);
            return Math.max(max1, max2);
        }
       
    }

 

예제 7) Binary Search

 

    // 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 (compResult == 0) {
                return middle;
            }
            else if (compResult < 0) {
                return binarySearch(items, target, begin, middle - 1);
            }
            else {
                return binarySearch(items, target, middle + 1, end);
            }
        }
    }