인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 보고 작성한 문서입니다.
Recursion Thinking(순환적으로 사고하기)
수학함수뿐 아니라 다른 많은 문제들을 recursion으로 해결할 수 있다.
-
모든 순환함수는 반복문(iteration)으로 변경 가능하다.
-
그 역도 성립함. 즉 모든 반복문은 recursion으로 표현 가능하다.
-
순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 한다.
-
하지만 함수 호출에 따른 오버레드가 있다.(매개변수 전달, 액티베이녀 프레임 생성 등)
문자열의 길이 계산
public static int length(String str){
//Base case
if(str.equals("")){
return 0;
}
//Recursice case
else{
return 1 + length(str.substring(1));
}
}
문자열을 화면에 출력하는 함수
public static void printChars(String str){
//Base case
if(str.length()==0){
return;
}
//Recursice case
else{
System.out.print(str.charAt(0));
printChars(str.substring(1));
}
}
문자열을 뒤집어서 화면에 출력하는 함수
public static void printCharsReverse(String str){
//Base case
if(str.length()==0){
return;
}
//Recursice case
else{
printCharsReverse(str.substring(1));
System.out.print(str.charAt(0));
}
}
2진수로 변환하여 출력(음이 아닌 정수 n)
public void printInBinary(int n){
//Base case
if(n<2){
System.out.print(n);
}
//Recursice case
else{
printInBinary(n/2);
System.out.print(n%2);
}
}
배열의 합 구하기(n은 배열의 크기)
public static int sum(int n, int[] data){
//Base case
if(n<-0){
return 0;
}
//Recursice case
else{
return sum(n-1, data) + data[n-1];
}
}
데이터파일로 부터 n개의 정수 읽어오기
public void readFrom(int n, int[] data, Scanner in){
//Base case
if(n==0){
return;
}
//Recursice case
else{
readFrom(n-1, data, in);
data[n-1] = in.nextInt();
}
}