반응형
Recursion vs Iteration
- 모든 순환함수는 반복문으로 변경 가능하다.
- 모든 반복문은 recursion으로 표현 가능하다.
- 순환함수는 복잡한 알고리즘을 단순하고 알기쉽게 표현하는 것을 가능하게 한다
- 함수 호출에 따른 오버헤드가 존재한다.(매개변수 전달, 액티베이션 프레임 생성 등)
자기 자신을 호출하는 함수(메서드)를 Recursion이라고 한다.
1
2
3
4
5
6
7
8
9
10
11
|
public class Code01{
public static void main(String [] args){
func();
}
public static void func(){
System.out.println("Hello....");
func();
}
}
|
cs |
Recursion은 위와 같은 코드를 보면 메서드안에 자기 자신을 다시 호출함으로 무한루프에 빠질 수 있다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
public class Code02{
public static void main(String [] args){
int n = 4;
func(n);
}
public static void func(int k){
if(k<=0){
return;
}else{
System.out.pringln("Hello....");
func(k-1);
}
}
}
|
cs |
위의 코드를 보면 Recursion이라고 항상 무한루프에 빠지는 것은 아니다.
1
2
3
4
5
6
7
8
|
Hello...
Hello...
Hello...
Hello...
|
cs |
코드의 결과는 Hello...를 4번 반복하고 종료된다.
무한루프에 빠지지 않으려면 2가지 조건을 만족해야 한다.
1. Base case : 적어도 하나의 자기자신을 호출하지 않고 recursion에 빠지지 않는 경우가 존재해야 한다.
2. Recursive case : recursion을 반복하다 보면 결국 base case로 수렴해야 한다.
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public class Code 03{
public static void main(String [] args){
int result = func(4);
System.out.print(result);
}
public static int func(int n){
if(n==0){
return 0; // n= 0 이면 총 합은 0 이될수 밖에 없다
}else{
return n + func(n-1);
}
}
|
cs |
ex_1 : n개 합을 구하는 메서드
1
2
3
4
5
6
7
8
9
10
11
12
13
14
|
public class Code 03{
public static void main(String [] args){
int result = func(4);
System.out.print(result);
}
public static int factorial(int n){
if(n<=0)
return 1;
else{
return n * factorial(n-1);
}
}
|
cs |
ex_2 : 펙토리얼 구하는 메서드
1
2
3
4
5
6
|
public static int factorial(int n){
if(n<2)
return n;
else{
return fibonacci(n-1) + fibonacci(n-2);
}
|
cs |
ex_3 : 피보나치 수열 구하는 메서드
1
2
3
4
5
6
7
8
9
10
11
12
|
public static double gcd(int m, int n){
if(m<n){
int tmp=m;
m=n;
n=tmp;
}
if(m%n==0)
return n;
else
return gcd(n, m%n);
}
|
cs |
ex_4 : 최대 공약수 구하는 메서드
반응형
'알고리즘 > Algorithm' 카테고리의 다른 글
Recursion의 응용 - 미로찾기 (0) | 2021.01.19 |
---|---|
2진검색 알고리즘 (0) | 2021.01.19 |
Recursion(순환)-3 (0) | 2021.01.19 |
Recursion(순환)-2 (0) | 2020.07.05 |
선형 시간 알고리즘 (0) | 2020.07.05 |