순환(Recursion) 알고리즘 : 재귀함수
- 모든 순환함수는 반복문(Iteration)으로 변경가능, 모든 반복문은 recursion으로 표현가능
- 순환함수는 복잡한 알고리즘을 단순하고 알기 쉽게 표현하는 것을 가능하게 함, 하지만 오버해드가 있음(매개변수 전달, 엑티베이션 프레임 생성)
(반복문에 비해 실행속도 불리, 경우에 따라 필요한경우도 있음)
- 순환함수가 되지 않기 위해 : 적어도 하나의 base case 존재, Recursion을 반복하다보면 결국 base case로 수렴
- 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라
public class Recursion1 {
public static void main(String [] args){
int result = func(4);
System.out.println(result);
}
public static int func(int n){
if(n==0)
return 0;
else
return n+func(n-1); //n이 0보다 크다면 0에서 n까지의 합은 0에서 n-1 까지의 합에 더한 것이다.
}
}
Factorial : n!
0! = 1
n! = n x (n-1)! , n>0
public static int factorial(int n){
if(n==0)
return 0;
else
return n * factorial(n-1);
}
Fibonacci Number
f0 = 0
f1=1
fn = fn-1 + fn-2 , n-1
public static int fibonacci(int n){
if(n<2)
return n;
else
return fibonacci(n-1) + fibonacci(n-2);
}
Euclid Method : 최대공약수
유클리드 방법 :
m>=n 인 두 양수의 정수 m, n에 대해서
m이 n 의 배수이면 gcd(m, n) =n 이고 그렇지 않으면
gcd(m,n) = cde(n, m%n) 이다.
public static double gcd(int m, int n){
if(m<n)
int temp=m; m=n; n=temp; //swap m and n
if(m%n ==0)
return n;
else
return gcd(n, m%n);
}
public static int gdc2(int p, int q){
if(q==0)
return p;
else
return gdc(q, p%q);
}
Recursive Thinking : 순환적으로 사고하기
수학함수 뿐 아니라 다른 많은 문제들을 recursion으로 해결할 수 있다.
문자열의 길이 계산
public static int length(String str){
if(str.equals("")){
return 0;
}
else{
return 1+ length(str.substring(1));
}
}
문자열 프린트
public static void printChars(String str){
if(str.length() ==0){
return ;
}
else{
System.out.print(str.charAt(0));
printChars(str.substring(1));
}
}
문자열 뒤집어 프린트
public static void printCharsReverse(String str){
if(str.length() ==0){
return ;
}
else{
printCharsReverse(str.substring(1));
System.out.print(str.charAt(0));
}
}
2진수로 변환하여 출력
public static void printInBinary(int n){
if(n<2){
System.out.print(n);
}
else{
printInBinary(n/2);
System.out.print(n%2);
}
}
배열데이터 정수들의 합
public static int sum(String n, int [] data){
if(n<0)
return 0;
else
return sum(n-1,data) + data[n-1];
}
순환 알고리즘의 설계 DESIGNING RECURSION
- 암시적(implicit) 매개변수를 명시적(explicit) 매개변수로 바꾸어라
매개변수 암시화 : 순차탐색
// [0, n-1] 보통 생략... 즉 암시적인 매개변수 >>> 생략가능.
int search(int [] data, int n, int target){
for(int i =0; i <n ; i++){
if (data[i] == target)
return i;
}
return -1;
}
매개변수의 명시화 : 순차탐색
int search(int [] items, int begin, int end, int target){
if(begin > end)
return -1;
else if (target ==items[begin])
return begin;
else if
return search(data, begin+1, end , target);
}
매개변수의 명시화 : 순차탐색 2
int search(int [] items, int begin, int end, int target){
if(begin > end)
return -1;
else if (target ==items[end])
return end;
else if
return search(data, begin, end-1 , target);
}
매개변수의 명시화 : 순차탐색 3
int search(int [] items, int begin, int end, int target){
if(begin > end)
return -1;
else if (target ==items[end])
return end;
else if
return search(data, begin, end-1 , target);
}
매개변수의 명시화 : 순차탐색 4
int search(int [] items, int begin, int end, int target){
if(begin > end)
return -1;
else if {
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);
}
}
매개변수의 명시화 : 최대값 찾기
int findMax(int [] items, int begin, int end){
if(begin == end)
return data[begin];
else
return Math.max(data[begin], findMax(data, begin+1, end)); // 첫번째 값을 제외한 나머지의 최대값
}
매개변수의 명시화 : 최대값 찾기 2
int findMax(int [] items, 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(djata,, middle+1, end);
return Math.max(max1, max2);
}
}
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 = terget.compareTo(items[middle]);
if(comResult ==0)
return middle;
else if (compResult <0)
return binarySearch(items, target, begin, middle-1);
else
return binarySearch(items, target, middle+1, end);
}
}
