public class Recursive2 {
// 2진수 출력
public static void main(String[] args) {
Recursive2 rc = new Recursive2();
rc.DFS(11);
}
public void DFS(int n){
if(n == 0){
return;
}else{
DFS(n / 2);
System.out.print(n % 2 + "");
}
}
}
2진수는 2로 나누면서 나머지 값을 왼쪽 부터 출력하기 떄문에
스택에 넣어서 제일 낮은값 부터 찍어주면 된다 그러므로 출력부분이 아래 오게 해주면 된다!
public class Recursive3 {
public static void main(String[] args) {
Recursive3 rc = new Recursive3();
System.out.println(rc.DFS(5));
}
public int DFS(int n){
if(n == 0){
return 1;
}else {
n = n * DFS(n - 1);
}
return n;
}
}
팩토리얼 찍는 문제
처음에는 sum 함수를 따로 주려고 했는데
그럴필요 없이 n이 0으로 가면 팩토리얼은 마지막에 1을 주기 때문에 1을 반환하고 그 1 값을 가지고
누적해서 곱해준다
그러면 처음에 5가 들어왔을때
5 = 5 * DFS(4) ※ DFS(4) = 4 * DFS(3)
이런식으로 누적해서 곱해주기때문에
5 * 4 * 3 * 2 * 1 을 만들어 줄 수 있다!
}else {
return n * DFS(n - 1);
}
else 부분을 이런식으로 바꿔줄 수 있다
public class Recursive4 {
public static void main(String[] args) {
Recursive4 rc = new Recursive4();
int n = 10;
for(int i=1; i<=n; i++){
System.out.print(rc.DFS(i) + " ");
}
}
public int DFS(int n){
if(n == 1 || n == 2){
return 1;
}else {
return DFS(n-1) + DFS(n-2);
}
}
}
피보나치 재귀
많이 해봤으므로 ... 마찬가지로 반복문으로 재귀함수를 이용해서 출력해 줄 수 있음
근데 알고리즘에서 풀어봤듯이 이렇게 풀면 나중가면 재귀를 너무 많이타서 시간 초과가 나올 수 있으므로
배열을 이용해서 풀자!!
'Algorithm' 카테고리의 다른 글
[재귀함수] 재귀함수 기초 - 4 ( 부분집합 DFS ) (0) | 2022.12.12 |
---|---|
[재귀함수] 재귀함수 기초 - 3 (0) | 2022.12.08 |
[재귀함수] 재귀함수 기초 - 1 (0) | 2022.12.07 |
[프로그래머스] 푸드 파이트 대회 (0) | 2022.11.29 |
[프로그래머스] 다음 큰 숫자 (0) | 2022.11.25 |