⚒ 자료구조 스터디 ⚒
📂재귀
✅재귀란
- 컴퓨터 과학에서 재귀란 자신을 정의할 때 자기 자신을 재참조하는 방법을 의미한다.
✅재귀함수란
- 재귀의 설명 그대로 함수에서 자기 자신을 다시 호출해 작업을 수행하는 방식이다.
- 주로 반복문을 구현할 때 사용한다.
❗재귀 알고리즘 -> 문제를 해결하기 위해 재귀 함수를 사용하는 알고리즘을 의미한다.❗
❓어디서 쓰나요❓
- 팩토리얼 (N! = N N-1 ... * 1)
- N까지의 자연수의 합
📂재귀함수의 장, 단점
✅구현
- java.util.Stack 클래스를 사용
- 배열이나 연결리스트 사용
🔎 장점
1. 코드의 가독성이 높아진다. 재귀적인 호출을 통해 코드를 간결하게 작성할 수 있다.
- 일부 알고리즘에서는 반복문을 사용하는 것보다 재귀 함수를 사용하는 것이 더 직관적이다.
🔎 단점
1. 재귀 함수는 함수를 호출할 때마다 스택에 새로운 프레임을 생성한다. 따라서, 스택이 너무 깊어질 경우에는 스택 오버플로우가 발생할 수 있다.
- 재귀 함수는 함수의 호출이 반복적으로 일어나기 때문에, 일반적으로 반복문을 사용하는 것보다 느리다.
❓스택 오버플로우란❓
Stack Overflow는 Stack 영역의 메모리가 지정된 범위를 넘어갈 때 발생한다.함수에서 지역 변수를 선언하면 지역 변수는 Stack 메모리에 할당되고 함수를 빠져나오면 Stack 메모리에서 해제된다.
만약 한 함수에서 너무 큰 지역 변수를 선언하거나 함수를 재귀적으로 무한정 호출하게 되면 stack overflow가 발생할 수 있다.
📐문제풀이
🚩백준: 실버5 - Q17478 재귀함수가 뭔가요?
문제
Q. JH 교수님은 재귀함수가 무엇인지 물어보는 학생들을 위한 작은 선물로 자동 응답 챗봇을 준비하기로 했다.
JH 교수님이 만들 챗봇의 응답을 출력하는 프로그램을 만들어보자.
입력
교수님이 출력을 원하는 재귀 횟수 N(1 ≤ N ≤ 50)이 주어진다.
예시
🔻 입력값 🔻
2
🔻 출력값 🔻
어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.
"재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
__"재귀함수가 뭔가요?"
__"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
__마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
__그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."
____"재귀함수가 뭔가요?"
____"재귀함수는 자기 자신을 호출하는 함수라네"
____라고 답변하였지.
____라고 답변하였지.
라고 답변하였지.
✅백준 - Q17478 문제풀이
🎯 처음 구상도
1. 반복수에 따라 underbar가 4칸씩 추가된다.
2. 반복 하는 문장 앞에 + 해서 underbar를 넣어준다.
3. 출력한다
❓문자열에 *를 사용하려 해서 애먹었다. static으로 선언 이후에 underbar += "____" 를 하자.
💻결과 코드
package recursion_function;
import java.io.BufferedReader;
import java.io.IOException;
import java.io.InputStreamReader;
import java.util.Scanner;
public class Silver5_Q17478 {
public static void main(String[] args) throws IOException {
BufferedReader br = new BufferedReader(new InputStreamReader(System.in));
int N = Integer.parseInt(br.readLine());
System.out.println("어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.");
recur(N);
}
static String underbar ="";
public static void recur(int N){
String line = underbar;
if(N == 0){
System.out.println(line+"\"재귀함수가 뭔가요?\"");
System.out.println(line+"\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.");
System.out.println(line+"마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.");
System.out.println(line+"그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"");
return;
}
System.out.println(line+"\"재귀함수가 뭔가요?\"");
System.out.println(line+"\"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.");
System.out.println(line+"마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.");
System.out.println(line+"그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"");
underbar+="____";
recur(N-1);
}
}
🚩백준: 실버4 - 별 찍기 19
문제
Q. 예제를 보고 규칙을 유추한 뒤에 별을 찍어 보세요.
조건
첫째 줄에 N(1 ≤ N ≤ 100)이 주어진다.
🔻입력 예시🔻
1
🔻출력 예시🔻
*
🔻입력 예시2🔻
2
🔻출력 예시🔻
🔻입력 예시2🔻
3
🔻출력 예시🔻
✅백준 - Q10994 문제풀이
🎯 처음 구상도
1. 조건 확인 (N이 1이 늘 때마다 *의 가로와 세로가 4씩 추가)
2. 좌표를 이용하기로 함 (2차원 배열)
3. 가로 첫줄과 마지막 줄, 세로 첫줄과 마지막 줄부터 생성
4. 2차원 배열의 각 기본값으로 공백을 넣음
7. 반복문 돌리면서 출력
❓ 90퍼센트에서 자꾸 실패를 함.
❌ 실패 이유 분석
N이 1일때와 중앙에 별을 넣어야된다는 생각에 잡혀, 조건 처리를 잘못함
⭕ 해결
- N이 1일때 조건문을 빼고, 반복문 안에서 처리
- 중앙에 임의로 별을 안박고, 반복문 안에서 처리
💻결과 코드
package recursion_function;
import java.util.Scanner;
public class Silver4_Q10994 {
static String[][] stars;
public static void main(String[] args) {
Scanner in = new Scanner(System.in);
int N = in.nextInt();
// if (N == 1) System.out.println("*");
// 요놈을 써놓고 깜빡함..
int length = 1;
length += (N-1) * 4;
stars = new String[length][length];
for (int i = 0; i < length; i++){
for (int j = 0; j < length; j++){
stars[i][j] = " ";
}
}
// stars[length / 2 + 1][length / 2 + 1] = "*";
print(0, length);
for (int i = 0; i < length; i++){
for (int j = 0; j < length; j++){
System.out.print(stars[i][j]);
}
System.out.println();
}
}
static void print(int N, int length){
for (int i = N; i < length; i++){
stars[N][i] = "*"; // 첫번째 가로줄
stars[i][N] = "*"; // 첫번째 세로줄
stars[length-1][i] = "*"; // 마지막 가로줄
stars[i][length-1] = "*"; // 마지막 세로줄
}
if (length == 1) return;
print(N+2, length-2);
}
}
