재귀함수란 자기 자신을 호출하는 함수. but, 항상 무한루프에 빠지는 것은 아님.
recursive method의 기본 구성
→ base case : 재귀 호출에서 빠져나가기 위한 경우
ex) if(n<1) { return 0 }
→ recursive case : 자신을 호출하는 함수를 포함하는 경우
ex) else { myself(n-1) }
recursive를 사용하여 풀 수 있는 문제들
→ Factorial n!
0! = 1
n! = n * (n-1)! (if n>0)
→ X의 n승
X의 0승 = 1
X의 n승 = X*X의 n-1승 (if n>0)
→ Fibonacci Number(피보나치 수)
F0 = 0
F1 = 1
Fn = Fn-1 + Fn-2 (if n>1)
→ Euclid Method 유클리드 호제법(최대공약수)
recursive thinking 순환적 사고
문자열의 길이 계산
if the string is empty
return 0;
else
return 1 plus the length of the string that excludes the first character;
public static int length(String str) {
if (str.equals(""))
return 0;
else
return 1 + length(str.substring(1))
}
str.substring(int startIndex) : str의 startIndex 문자부터 끝까지의 문자열을 리턴
str.substring(int startIndex, int endIndex) : str의 startIndex 문자부터 endIndex의 문자까지의 문자열을 리턴
문자열의 프린트
public static void printChars(String str) {
if (str.length() == 0)
return;
else {
System.out.println(str.charAt(0));
printChars(str.substring(1));
}
}
** str.charAt(int index) : index 위치의 문자 1개를 리턴
문자열을 뒤집어서 프린트
public static void printCharsReverse(String str) {
if (str.length() == 0)
return;
else {
printCharsReverse(str.substring(1));
System.out.println(str.charAt(0));
}
}
2진수로 변환하여 출력
public void printInBinary(int n) {
if (n<2)
System.out.print(n);
else {
printInBinary(n/2); // n을 2로 나눈 몫을 먼저 2진수로 변환하여 출력한 후
System.out.print(n%2); // n을 2로 나눈 나머지를 인쇄한다.
}
}
배열의 합 구하기
// data[0]에서 data[n-1]까지의 합
public static int sum(int n, int [] data) {
if (n<=0)
return 0;
else
return sum(n-1, data) + data[n-1];
}
Recursion vs. Iteration
→ 모든 순환함수는 반복문(iteration)으로 변경 가능
→ 그 역도 성립함. 즉 모든 반복문은 recursion으로 표현 가능함.
→ 순환함수는 복잡한 알고리즘을 단순하고 알기 쉽게 표현하는 것을 가능하게 함.
→ 하지만 함수 호출에 따른 오버헤드(overhead)가 있음(매개변수 전달, 액티베이션 프레임 생성 등)
암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꿔라.
순차 탐색(검색) sequential search
: 정렬되어 있지 않은 배열 안의 어떤 값을 찾을 때 순서대로 하나씩 검사하는 알고리즘.
→ 이 함수의 미션은 data[0]부터 data[n-1] 사이에서 target을 검색한다. 하지만 검색 구간의 시작 인덱스 0은 보통 생략한다. 즉 0은 '암시적 매개변수' 이다.
int search(int[] data, int n, int target) {
for(i = 0; i < n; i++) {
if(data[i] == target)
return i;
return -1;
}
매개 변수의 명시화 : 순차 탐색
→ 이 함수의 미션은 data[begin]부터 data[end]사이에서 target을 검색한다. 즉, 검색구간의 시작점을 명시적(explicit)으로 지정한다.
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);
}
순차 탐색의 다른 버전
→ 중간에서 부터 앞 부분을 먼저 검색하고 그 안에서 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);
}
}
매개 변수의 명시화 : 최대값 구하기
→ 이 함수의 미션은 data[begin]과 data[end]사이에서 최대값을 찾아 반환하는 것이다. begin≤end라고 가정한다.
int findMax(int[] data, int begin, int end) {
if (begin == end)
return data[begin];
else {
return Math.max(data, 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);
이진 검색 binary search
→ 순차적으로 정렬된 배열의 시작과 끝 사이에서 어떤 값 a를 찾을 때, 그 배열의 중간의 값 m과 a를 비교하여
a < m 라면 배열의 시작부터 m까지의 값 사이에 a가 있을 것이고
a > m 라면 m부터 배열의 끝까지의 값 사이에 a가 있을 것임
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);
}
}
string1.compareTo(string2)은
string1 == string2일 때, 0을 리턴
string1 > string2일 때, 1을 리턴
string1 < string2일 때, -1을 리턴
이 포스트는 인프런의 알고리즘 강좌 '권오흠님의 영리한 프로그래밍을 위한 알고리즘' 를 정리한 내용입니다.