본문 바로가기

알고리즘/Algorithm

Recursion(순환)-3

반응형

- 적어도 하나의 base case, 즉 순환되지 않고 종료되는 case가 있어야 한다.

- 모든 case는 결국 base case로 수렴해야 한다.

 

 

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

0 ~ n-1  -> 암시적

begin ~ end  -> 명시적

 

순차탐색

1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
public int search(int[] data, int n, int target) {
    for(int i = 0; i < n; i ++){
        if(data[i] == target){
            return 1;
        }
    }
    return -1;
}
 
 
public 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);
}
cs

 

최대값 찾기

1
2
3
4
5
6
7
8
public 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));
    }
}
cs
1
2
3
4
5
6
7
8
9
10
11
public 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);
        }
    }
cs

 

반응형

'알고리즘 > Algorithm' 카테고리의 다른 글

Recursion의 응용 - 미로찾기  (0) 2021.01.19
2진검색 알고리즘  (0) 2021.01.19
Recursion(순환)-2  (0) 2020.07.05
선형 시간 알고리즘  (0) 2020.07.05
Recursion(순환)-1  (0) 2020.06.27