재귀 함수
- 함수 내에서 해당 함수를 또 호출
- 반복의 depth가 랜덤일 때 사용(인자 or 배열로 depth를 컨트롤한다)
- 재귀 함수는 종료 조건을 설정하지 않으면 무한하게 자기 자신을 호출
- 기저조건에서 재귀가 중단
-기저 조건: 특정 조건일 때 재귀 중단
-유도파트 : 재귀 실행
✅ for문과 유사한 형태로 재귀함수 작성 가능
- bottom -> up 방식
//for문과 유사한 형태로 재귀함수 작성 가능
// bottom -> up 방식
static int N =5;
public static int sum1(int n) {
if(n==N)return n;
return n +sum1(n+1);
}
------------------------------------------
public static void main(String[] args) {
int sum = 0;
for(int i =1; i<=N; i++) {
sum += i ;
}
System.out.println(sum);
System.out.println(sum1(1));
: 두개 모두 1+2+3+4+5 의 활동을 통하여 15의 결과 출력
N 이 5일때의 재귀 함수의 모습
1+sum(2)
2+ sum(3)
3 + sum(4)
4+ sum(5)
5
-top - > down
public static int sum2(int n) {
if(n==0)return n;
return n +sum2(n-1);
}
------------------------------------------------------------------
sum = 0;
for(int i =N; i>=0; i--) {
sum += i ;}sum2(5) / N=5 결과에 대하여
: 두개 모두 5+4+3+2+1의 활동을 통하여 15의 결과 출력
- 특정 조건을 만족할 때 재귀가 진행되는 구조
✅ while 문과 유사한 형태로 재귀함수 작성 가능
int count = 0;
while (count <11);
System.out.println(count);
(count++);
특정 조건을 만족 할 때 재귀가 진행되겠끔 구조 작성 가능
//bottom ->up
public static void print3(int num) {
if(num<=N) {
System.out.print(num +" ");
print3(num+1);
}
}
-------------------------------------------------------------------------------------------
//top - > down
public static void print4(int num) {
if(num>-1) {
System.out.print(num +" ");
print4(num-1);
}
}
- for 문과 재귀함수의 차이
for문의 경우 한번 반복하면 끝이지만 재귀함수는 자신의 함수로 다시 돌아옵닌다.
- 재귀함수는 함수를 반복적으로 호출하기 때문에 스택 메모리를 사용
- for문의 경우 hip 메모리 사용
=> for 문 보다 재귀함수가 시간이 더 걸립니다.
그러나 재귀함수의 경우 사용시 변수의 사용이 줄고 가독성이 좋아지며
알고리즘 자체가 재귀적인 표현이 자연스러운 경우 사용 합니다.
* 재귀를 호출하기 전 처리해줘야한는 상황 끝나고 호출해야 하는 상황이 둘다를 잘 확인하여 재귀함수 사용!!!
- 재귀함수를 이용한 문제 풀이
https://www.acmicpc.net/problem/17478
=> 백준 문제 확인
public class Main {
static int N ;
public static void main(String[] args) throws Exception {
// System.setIn(new FileInputStream("res/backjoon/"));
BufferedReader in =new BufferedReader(new InputStreamReader(System.in));
N= Integer.parseInt(in.readLine());
print(0,"어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.");
recursive(0);
}
private static void recursive(int n) {
print(n,"\"재귀함수가 뭔가요?\"");
if(n==N) {
print(n,"\"재귀함수는 자기 자신을 호출하는 함수라네\"");
}else {
print(n,"\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.");
print(n,"마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.");
print(n,"그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"");
recursive(n+1);
}
print(n,"라고 답변하였지.");
}
private static void print(int n, String msg) {
for (int i = 0; i <n; i++) {
System.out.print("____");
}
System.out.println(msg);
}
}입력 2
출력
어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.
"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
____"재귀함수가 뭔가요?"
____"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
____마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
____그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
________"재귀함수가 뭔가요?"
________"재귀함수는 자기 자신을 호출하는 함수라네"
________라고 답변하였지.
____라고 답변하였지.
라고 답변하였지.
: 해당 문제의 핵심은 반복과 ----바의 증감 (깊이가 늘어났다가 줄어듬) 입니다.이를 해결하기 위해 재귀함수 호출 할 때와 호출이 끝난 후의 차이를 이용하여 ----의 길이를 조절해 보았습니다.
재귀함수는 메소드가 차곡차곡 쌓이고 조건에 다다를때부터는 차곡차곡 빠지는 특성을 갖고 있습니다.
|
private static void print(int n, String msg) {
for (int i = 0; i <n; i++) { System.out.print("____"); } System.out.println(msg); } |
: 우선 print 함수를 통한 메세지 앞 호출수에 따른 ----길이 메서드 작성
어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.
해당 문구가 가장 먼저 한번 출력
| print(0,"어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다."); recursive(0); 0번이었을 때의 첫번째와 언더바가 없는 recursive(반복되는 부분) 호출 |
N번째 질문에 대한 대답에 대해선
"재귀함수는 자기 자신을 호출하는 함수라네"
라는 다른 답변이 나와야 한다.
| private static void recursive(int n) { print(n,"\"재귀함수가 뭔가요?\""); if(n==N) { print(n,"\"재귀함수는 자기 자신을 호출하는 함수라네\""); |
그 이후
"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
반복된다.
|
private static void recursive(int n) {
print(n,"\"재귀함수가 뭔가요?\""); if(n==N) { print(n,"\"재귀함수는 자기 자신을 호출하는 함수라네\""); }else { print(n,"\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어."); print(n,"마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지."); print(n,"그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\""); recursive(n+1); } |
:재귀 함수를 통하여 "-----" 깊이가 깊어지는 부분 표현
recursive(n+1); 을 통하여 재귀함수 진행
라고 답변하였지.
에 대해서는 재귀에서 나와 깊이가 줄어 들어야 한다.
재귀 함수가 끝나고
| print(n,"라고 답변하였지."); |
해당 문구 출력 하여
재귀 함수가 종료되며 다시 돌아올 때, n 값이 줄어들며 들여쓰기가 점차 줄어듭니다.
'Cs기본지식 > 알고리즘' 카테고리의 다른 글
| 자바 자료구조 / Graph ,Tree 알아보기 (1) | 2025.02.19 |
|---|---|
| 자바 알고리즘 Subset 알아보기 (0) | 2025.02.18 |
| 자바 알고리즘 /순열과 조합 (0) | 2025.02.17 |
| 정렬 알고리즘 이해하기 : 기본 구조 및 종류 (0) | 2025.02.17 |
| 자바 알고리즘 Datastructure (0) | 2025.02.17 |