[바킹독 재귀] 재귀 복습

바킹독님 재귀 강의 https://blog.encrypted.gg/943

[실전 알고리즘] 0x0B강 - 재귀

보고 재귀, 백트래킹 틀 익히자!

 

[재귀 파트]

 

순서에 따라 정해져 있는 스택 문제 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

[백준] 1629번 곱셈 C++

[계획]

곱셈 문제, Z 문제 풀고 재귀 틀 익히기

 

출처) 바킹독님 재귀 강의 https://blog.encrypted.gg/943

[실전 알고리즘] 0x0B강 - 재귀