[바킹독 재귀] 재귀 복습
바킹독님 재귀 강의 https://blog.encrypted.gg/943
보고 재귀, 백트래킹 틀 익히자!
[재귀 파트]
순서에 따라 정해져 있는 스택 문제 vs 귀납법
귀납법) 1번 도미노 쓰러져요. k번 도미노 쓰러지면 k+1번 도미노도 쓰러져요.
절차지향적 사고vs귀납법 사고
절차지향적 사고는 그대로 함수를 한줄 한줄 따라가면 된다.
귀납적 사고는 다음 슬라이드 부분을 참고하자.
나는 초보자여서 규칙성을 찾고 그걸 귀납적 사고에 적용할 것이다.
n=1일 때 1이 출력되므로 func1(1)이 1을 출력하고,
func1(2)는 2를 출력하고 func1(1)에서 나오는 1을 출력해서 2 1 이렇게 출력한다.
func1(3)은 3을 출력하고 func1(2)는 2 1을 출력하게 되어서 3 2 1 이렇게 출력한다.
....규칙성 발견!
func(k)는 k k-1 k-2 ... 1을 출력하면
func(k+1)은 k+1 k k-1 ... 1을 출력한다.
[재귀 함수의 조건]
특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야 한다 (Base condition) 모든 입력은 base condition
void func1(int n) {
if(n==0) return;
cout<<n<<' ';
func1(n-1);
}
[재귀 Tip]
명확한 함수 정의) 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 한다.
모든 재귀 함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있다.
재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지만 메모리/시간 면에서는 손해를 본다.
한 함수가 자기 자신을 여러 번 호출하게 되면 비효율적일 수 있다.
이미 계산한 거 또 하니까 답이 없다. 다이나믹 프로그래밍으로 O(n)으로 해결하기 나중에
다음 시리즈 링크) https://armembedded.tistory.com/151
[계획]
곱셈 문제, Z 문제 풀고 재귀 틀 익히기
출처) 바킹독님 재귀 강의 https://blog.encrypted.gg/943