재귀함수란?
- 자신이 자신을 호출하는 함수
- 재귀함수는 stack구조를 사용
- 재귀함수에는 함수가 더 이상 반복되지않는 경우인 기저 조건이 적어도 하나는 있어야 함
재귀함수와 스택프레임
- 재귀호출을 할 때마다 새로운 호출 스택이 메모리 스택에 생성
- 각 호출 스택에는 해당 호출의 인수와 지역변수 등이 저장
- 가장 최근에 호출된 함수가 스택의 맨 위에 위치
- 재귀 호출에서 함수가 실행을 마치고 반환되면 해당 함수에 대한 호출 스택이 메모리에서 제거 ( 호출 스택 해제 )
- 재귀 호출이 많이 일어나면 호출 스택이 많이 쌓이고 메모리 사용량을 늘리게 되어 메모리 낭비라는 부작용이 있다.
재귀함수 예시
1. 출력 : 3 2 1
public class Main {
public void DFS(int n) {
if(n==0)return; // return : 함수 종료
else {
System.out.println(n+ " ");
// 무한반복
DFS(n-1);
}
}
public static void main(String[] args) {
Main T = new Main();
T.DFS(3);
}
}
2. 출력 : 1 2 3
public class Main {
public void DFS(int n) {
if(n==0)return; // return : 함수 종료
else {
// 무한반복
DFS(n-1);
System.out.println(n+ " ");
}
}
public static void main(String[] args) {
Main T = new Main();
T.DFS(3);
}
}
1번과 2번의 차이
1번은 재귀 호출이 기저 조건에 도달할 때까지 계속 호출되고, 함수가 종료될 때마다 해당 호출의 매개변수 n 값을 출력한다. 따라서 3 2 1 로 출력된다.
2번은 재귀 호출이 기저 조건에 도달한 후 반환되면 호출 스택이 메모리에서 제거되면서 저장되어있던 정보를 출력한다. 따라서 1 2 3 으로 출력된다.
이진수 재귀함수
public class Main {
public void DFS(int n) {
if(n==0) return;
else {
DFS(n/2);
System.out.print(n%2+ " ");
}
}
public static void main(String[] args) {
Main T = new Main();
T.DFS(11);
}
}
- DFS(11)에서 n은 11이므로, DFS(11/2)인 DFS(5)를 호출
- DFS(5)에서 n은 5이므로, DFS(5/2)인 DFS(2)를 호출
- DFS(2)에서 n은 2이므로, DFS(2/2)인 DFS(1)을 호출
- DFS(1)에서 n은 1이므로, DFS(1/2)인 DFS(0)을 호출
- DFS(0)에서는 n이 0이므로 재귀 호출이 종료되고 함수가 리턴
- 역순으로 각 호출의 결과를 출력 / 1011
팩토리얼 재귀함수
public class Main {
public int DFS(int n) {
if(n==1) return 1;
else return n*DFS(n-1);
}
public static void main(String[] args) {
Main T = new Main();
System.out.println(T.DFS(5));
}
}
DFS(5) / 5 * DFS(4)
DFS(4) / 4 * DFS(3)
DFS(3) / 3 * DFS(2)
DFS(2) / 2 * DFS(1)
DFS(1) / 1
로 진행후 return 값을 받게 된다.
1
2 * 1 = 2
3 * 2 = 6
4 * 6 = 24
5 * 24 = 120
즉 DFS(n-1)에 축적을 받는 셈이다.
1 >> 1 * 2 >> 1 * 2 * 3 >> 1 * 2 * 3 * 4 >> 1 * 2 * 3 * 4 * 5
답 : 120
피보나치 재귀함수
- DFS(n-2) 호출을 먼저 수행하고, 이후에 DFS(n-1) 호출을 수행
ex ) n = 5일 때
1. 단순한 재귀 함수 사용
- 같은 값에 대해 중복된 계산을 수행하기 때문에 성능이 좋지 않음
- 메모이제이션을 사용하지 않으므로 중복 계산을 효율적으로 제거하지 않음
public class Main {
public int DFS(int n) {
if(n==1) return 1;
else if(n==2) return 1;
else {
return DFS(n-2)+DFS(n-1);
}
}
public static void main(String[] args) {
Main T = new Main();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for( int i=1; i<=n; i++ ) {
System.out.print(T.DFS(i) + " ");
}
}
}
1. DFS(1)
- if(n==1) return 1;
2. DFS(2)
- else if(n==2) return 1;
3. DFS(3)
- DFS(n-2)를 먼저 실행, DFS(1)이므로 1리턴
- DFS(n-1)를 실행, DFS(2)이므로 return 1
- 1+ 1 =2 , 2 리턴
4. DFS(4)
- DFS(n-2)를 먼저 실행, DFS(2)이므로 1리턴
- DFS(n-1)를 실행, DFS(3)이므로
- DFS(1)은 1리턴
- DFS(2)는 1리턴
- 둘을 합쳐서 2리턴
- DFS(4)는 1 + 2 =3 리턴
5. DFS(5)
- DFS(n-2)를 먼저 실행, DFS(3)이므로
- DFS(1)은 1리턴
- DFS(2)는 1리턴
- 둘을 합쳐서 2리턴
- DFS(n-1)를 실행, DFS(4)이므로
- DFS(2)는 1리턴
- DFS(3)은
- DFS(1)은 1리턴
- DFS(2)는 1리턴
- 둘을 합쳐서 2리턴
- DFS(2)+DFS(3) = 3리턴
- DFS(5) 는 2 + 3 = 5 리턴 1 1 2 3 5 출력
6. 1 1 2 3 5 출력
중복 계산이 발생!
2. 메모이제이션을 사용하여 중복된 계산을 효율적으로 제거
- 각 계산된 값을 배열에 저장하고 필요할 때마다 배열에서 값을 가져와 사용
- 조건문을 추가하여, 이미 계산된 값을 배열에 저장한 후 해당 값이 있을 경우에는 바로 반환
- 중복된 계산이 한 번만 수행되므로 성능 개선
public class Main {
static int[] fibo;
public int DFS(int n) {
// 이미구한 값
if(fibo[n]>0) return fibo[n];
if(n==1) return fibo[n]=1;
else if(n==2) return fibo[n]=1;
else {
return fibo[n]=DFS(n-2)+DFS(n-1);
}
}
public static void main(String[] args) {
Main T = new Main();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
fibo = new int[n+1];
for( int i=1; i<=n; i++ ) {
System.out.print(T.DFS(i) + " ");
}
}
}
1. DFS(1)
- if(n==1) return fibo[1]=1;
2. DFS(2)
- else if(n==2) return fibo[2]=1;
3. DFS(3)
- return fibo[3] = DFS(1) + DFS(2)
- DFS(n-1)를 실행, DFS(2)이므로 return 1
- 1+ 1 =2 이고 이 값이 fibo[3]에 저장된 후 리턴
4. DFS(4)
- DFS(n-2)를 먼저 실행, DFS(2)이므로 1리턴
- DFS(n-1)를 실행, DFS(3)이므로 2리턴 (이미 fibo[3]에 DFS(3)값이 저장되어있기 때문)
- 1 + 2 =3 이고 이 값이 fibo[4]에 저장된 후 리턴
5. DFS(5)
- DFS(n-2)를 먼저 실행, DFS(3)이므로 2리턴 (이미 fibo[3]에 DFS(3)값이 저장되어있기 때문)
- DFS(n-1)를 실행, DFS(4)이므로 3리턴 (이미 fibo[4]에 DFS(4)값이 저장되어있기 때문)
- DFS(5) 는 2 + 3 = 5 리턴
6. 1 1 2 3 5 출력
참고) int[] fibo; 가 아닌 static int[] fibo; 인 이유
- main 메서드는 정적 메서드이며, 정적 메서드에서 인스턴스 변수에 직접적으로 접근 가능
- 따라서 main 메서드에서 인스턴스 변수인 fibo에 접근하려고 하면 컴파일 오류가 발생
- fibo 배열을 static으로 선언하여 클래스 수준에서의 변수로 만들면 모든 객체가 이 변수를 공유 가능
피보나치 수열을 for문으로 구하기
public class Main {
public int[] solution(int n) {
int[] answer = new int[n];
answer[0]=1;
answer[1]=1;
for( int i=2; i<n; i++ ) {
answer[i]=answer[i-2]+answer[i-1];
}
return answer;
}
public static void main(String[] args) {
Main T = new Main();
Scanner sc = new Scanner(System.in);
int n = sc.nextInt();
for(int x : T.solution(n)) {
System.out.print(x+ " ");
}
}
}
피보나치 수열 구현 시 재귀함수보다 for문을 사용하는 것이 더 성능이 좋은 이유
- 스택 프레임이 생성되지 않으므로 스택 오버플로우 문제가 발생하지 않는다.
- 반복문을 사용하면 메모리 사용량이 증가하지 않으며, 각 항을 한 번만 계산하므로 중복 계산 문제도 발생하지 않는다.따라서 성능 면에서도 반복문을 사용하는 것이 더 효율적이다.
- 일반적으로 더 직관적이고 이해하기 쉽다.
'코딩테스트 및 알고리즘' 카테고리의 다른 글
| DFS 부분 집합 구하기 (0) | 2024.02.21 |
|---|---|
| DFS (0) | 2024.02.20 |
| 결정 알고리즘 2 (0) | 2024.02.18 |
| 결정 알고리즘 (0) | 2024.02.16 |
| 이분 검색 (0) | 2024.02.15 |
