인프런의 영리한 프로그래밍을 위한 알고리즘 강좌를 보고 작성한 문서입니다.
Recursion
-
자기 자신을 다시 호출하는 함수(혹은 메소드)
-
순환, 재귀함수라고도 불린다.
-
재귀함수를 활용 할 수 있는 곳
-
x의 n승을 계산 하는 함수
-
피보나치…등
-
void func(){
func();
}
잘못 짜면 아래와 같이 무한 루프에 빠질 수 있다.
public static void main(String[] args){
func();
}
public static void func(){
System.out.println("Hello...");
}
<출력>
Hello...
Hello...
Hello...
Hello...
.
.
.
무한루프에 빠지지 않기 위한 조건
-
Base case:적어도 하나의 recursion에 빠지지 않는 경우가 존재해야 한다.
-
Recursice case: recursion을 반복하다 보면 결국 base case로 수렴해야 한다.
public class Code01{
public static void main(String[] args){
func(4);
}
public static void func(int n){
//Base case
if(n<=0){
return;
}
//Recursice case
else {
System.out.println("Hello..");
func(n-1);
}
}
}
<출력>
Hello..
Hello..
Hello..
Hello..
n에서 0까지 더하는 함수
public class Code01{
public static void main(String[] args){
int result = func(4);
System.out.print(result);
}
public static int func(int n){
//Base case
if(n==0){
return 0;
}
//Recursice case
else {
return n + func(n-1);
}
}
}
<출력>
10
factorial
public static int factorial(int n){
if(n==0){
return 1;
} else{
return n*factorial(n-1);
}
}
fibonacci
public int fibonacci(int n){
if (n<2){
return n;
} else{
return fibonacci(n-1) + fibonacci(n-2);
}
}
최대 공약수
public static double gcd(int m, int n){
if (m<n){ //swap m and n
int tmp = m;
m = n;
n = tmp;
}
if (m%n==0){
return n;
} else{
return gcd(n, m%n);
}
}
m>=n인 두 양의 정수 m과 n에 대해서 m이 n의 배수이면 gcd(m,n)=n 이고,
그렇지 않으면 gcd(m,n) = gcd(n, m%n) 이다.
더 간단한 버전
public static int gcd(int p, int q){
if(q==0){
return p;
} else {
return gcd(q, p%q);
}
}