조건
1.
적어도 1개의 base case 가 존재해야한다. 즉, 순환되지 않고 종료되는 케이스가 있어야 한다.
2.
모든 케이스는 결국 base case 로 수렴해야한다.
기억하기
•
암시적 매개변수를 명시적 매개변수로 바꾸어라!
1. 순차탐색
•
순차 탐색에서의 미션은 0부터 n-1 배열 사이에서 타겟을 찾는 것이다. 하지만 이 검색 구간의 시작 인덱스 0은 보통 생략한다. 즉, 여기서 0이 암시적 매개변수가 된다.
•
이렇게 암시적으로 표현된 변수를 아래와 같이 명시화하는 것이 필요하다. 시작 인덱스를 명확하게 매개변수로 전달한다.
•
왜 필요할까?
◦
맨 처음 재귀함수를 호출할 때에는 0부터 시작하겠지만, 그 다음번부터 호출할 때에는 시작점이 한칸씩 뒤로 밀리게 된다.
◦
따라서 이 함수가 한번만 호출될때를 생각하지 말고, 계속 반복되어 호출될 것을 생각하고 매개변수를 디자인 해야한다.
◦
일단 매개변수를 명확하게 만들고 나중에 필요 없을 때, 삭제해주는 방법이 좋다.
package practice.algorithm.recursion;public class SearchFromBegin { public static void main(String[] args) { String s = "elephant"; char target = 'p'; System.out.println("search(s, 0, s.length(), target) = " + search(s, 0, s.length()-1, target));; } private static int search(String s, int begin, int end, char target) { if (begin >= end) { return -1; } if (s.charAt(begin) == target) { return begin; } return search(s, begin+1, end, target); } /** * search(s, 0, s.length(), target) = 3 * */}
Java
복사
뒤에서부터 탐색하는 방법
package practice.algorithm.recursion;public class SearchFromEnd { public static void main(String[] args) { String s = "elephant"; char target = 'p'; System.out.println("search(s, 0, s.length(), target) = " + search(s, 0, s.length()-1, target)); } private static int search(String s, int begin, int end, char target) { if (begin >= end) { return -1; } if (s.charAt(end) == target) { return end; } return search(s, begin, end-1, target); } /** * search(s, 0, s.length(), target) = 3 * */}
Java
복사
가운데부터 탐색하는 방법
package practice.algorithm.recursion;public class SearchFromMiddle { public static void main(String[] args) { String s = "elephant"; char target = 't'; System.out.println("search(s, 0, s.length(), target) = " + search(s, 0, s.length(), target)); } private static int search(String s, int begin, int end, char target) { if (begin > end) { return -1; } int middle = (begin + end) / 2; if (s.charAt(middle) == target) { return middle; } int index = search(s, begin, middle-1, target); if (index != -1) { return index; } return search(s, middle + 1, end, target); } /** * search(s, 0, s.length(), target) = 7 * */}
Java
복사
2. 최대값 찾기
처음부터 탐색하는 방법 - 일반적
package practice.algorithm.recursion;public class SearchMaxFromBegin { public static void main(String[] args) { int[] arr = new int[]{1, 100, 55, 4, -100}; System.out.println("findMax(arr, 0, arr.length-1) = " + findMax(arr, 0, arr.length - 1));; } private static int findMax(int[] arr, int begin, int end) { if (begin == end) { return arr[begin]; } return Math.max(arr[begin], findMax(arr, begin+1, end)); } /** * findMax(arr, 0, arr.length-1) = 100 * */}
Java
복사
가운데부터 탐색하는 방법
package practice.algorithm.recursion;public class SearchMaxFromMiddle { public static void main(String[] args) { int[] arr = new int[]{1, 100, 55, 4, -100}; System.out.println("findMax(arr, 0, arr.length-1) = " + findMax(arr, 0, arr.length - 1));; } private static int findMax(int[] arr, int begin, int end) { if (begin == end) { return arr[begin]; } int middle = (begin + end) / 2; int max1 = findMax(arr, begin, middle); int max2 = findMax(arr, middle+1, end); return Math.max(max1, max2); } /** * findMax(arr, 0, arr.length-1) = 100 * */}
Java
복사
3. 이진 탐색
package practice.algorithm.recursion;public class BinarySearch { public static void main(String[] args) { String[] strings = new String[]{"a", "v", "e", "p", "w", "b"}; String target = "w"; System.out.println("binarySearch(strings, target, 0, strings.length-1) = " + binarySearch(strings, target, 0, strings.length - 1));; } private static int binarySearch(String[] strings, String target, int begin, int end) { int middle = (begin + end) / 2; int result = target.compareTo(strings[middle]); if (result == 0) { return middle; } if (result < 0) { return binarySearch(strings, target, begin, middle-1); } return binarySearch(strings, target, middle+1, end); }}
Java
복사