문제이해
입력 : 재귀 횟수 N(1 ≤ N ≤ 50)
출력 : "재귀함수가 뭔가요?"
"잘 들어보게. 옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.
마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.
그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어."라고 답변하였지.
위와 같은 문구를 재귀 횟수만큼 반복한다.
마지막 줄에 라고 답변하였지는 반복 후에 마무리 닫는 형태로 출력하도록 하며 2번째 반복부터 ____ (_)를 4번 작성해서 차이점을 주도록 한다.
재귀
하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘
재귀 함수의 조건
- 특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 함(Base condition)
- 모든 입력은 Base condition으로 수렴해야 함.
=> 종료되는 조건이 호출되지 않도록 해야된다.
=> 준수하지 않으면 런타임 에러 발생
수학적 귀납법
왜 도미노가 쓰러짐?
이유1) 1 -> 2 -> 3 -> 4
이유2) 1번 도미노가 쓰러진다.
k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다.
void func(int n){
if(n==0) return;
cout<< n << ' ';
func(n-1);
}절차지향적 사고
3출력 -> func(2) -> 2출력 -> func(1) -> 1출력 -> func(0)
귀납적 사고
func(1)이 1을 출력한다.
func(k)가 k,k-1,k-2 ... 1을 출력한다.
func(k+1)가 k+1,k,k-1,k-2 ... 1을 출력한다.
k+1 출력 -> func(k)호출 = k,k-1,k-2 ... 1 출력
팁
- 함수를 명확하게 -> 정의 함수의 인자 어떤것? 어디까지 계산한 후 자기 자신에게 넘기는지
- 모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있음
- 한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있음 -> 이미 계산한 것을 다- 시 계산하는 경우 빈번함
- 재귀함수가 자기자신을 부를 때 스택 영역에 계속 누적이 됨 -> 스택 영역의 메모리가 < 1MB
문제풀이
문제코드
#include <iostream>
using namespace std;
// 입력값 재귀 횟수 N (1<=N<=50)
int N;
void line(const char* str, int count) {
for (int i = 0; i < count; ++i) {
cout << "____";
}
cout << str;
}
void recur(int cnt) {
line("\"재귀함수가 뭔가요?\"\n", cnt);
if (N == cnt) {
line("\"재귀함수는 자기 자신을 호출하는 함수라네\"\n", cnt);
}
else {
line("\"잘 들어보게.옛날옛날 한 산 꼭대기에 이세상 모든 지식을 통달한 선인이 있었어.\n", cnt);
line("마을 사람들은 모두 그 선인에게 수많은 질문을 했고, 모두 지혜롭게 대답해 주었지.\n", cnt);
line("그의 답은 대부분 옳았다고 하네. 그런데 어느 날, 그 선인에게 한 선비가 찾아와서 물었어.\"\n", cnt);
recur(cnt + 1);
}
line("라고 답변하였지.\n", cnt);
}
int main() {
ios::sync_with_stdio(0);
cin.tie(0);
cin >> N;
cout << "어느 한 컴퓨터공학과 학생이 유명한 교수님을 찾아가 물었다.\n";
recur(0);
}
헷갈린 점
질문(아직 해결X)
질문 해결
Hello