[알고리즘 공부] 실전 알고리즘 11강-재귀

바킹독님이 올려주신 [실전 알고리즘] 영상을 보면서 공부한것을 기록
모든 사진은 바킹독님의 블로그에서 가져왔습니다.
https://blog.encrypted.gg/

---

알고리즘 설명

재귀 : 하나의 함수에서 자기 자신을 다시 호출해 작업을 수행하는 알고리즘

첫번째 도미노가 쓰러지면 모든 도미노가 쓰러지는것을 증명하는 방법에는 2가지가 있다.

1. 1번 도미노가 쓰러지면 2번 도미노가 쓰러지고, 2번 도미노가 쓰러지면 3번 도미노가 쓰러지고.. k번 도미노가 쓰러지면 k+1번 도미노가 쓰러진다. 따라서 모든 도미노가 쓰러진다.
2. 1번 도미노가 쓰러진다. k번 도미노가 쓰러진다. k+1번 도미노도 쓰러진다. 따라서 모든 도미노가 쓰러진다.

앞으로는 1번과 같은 절차지향적인 사고를 탈피하고 수학적 귀납법 사고를 가져야한다.

재귀함수의 조건 : 특정 입력에 대해서 자기 자신을 호출하지 않고 종료되어야함. 이를 base condition이라고 하며 모든 입력은 base condtion으로 수렴해야 한다.

재귀에 대한 정보 1

1. 함수의 인자로 어떤 것을 받고 어디까지 게산한 후 자기 자신을 넘겨줄지 명확하게 정해야함
2. 모든 재귀함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있음
3. 재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지만 메모리/시간에서는 손해를 봄

재귀에 대한 정보 2

1. 한 함수가 자기 자신을 여러번 호출하게 되면 비효율적일 수 있음 -> 재귀는 같은 함수를 여러번 호출하게 되므로 시간복잡도가 O(2^n)이다. 이는 dp를 이용해서 O(n)으로 해결할 수 있다.

재귀에 대한 정보 3

1. 재귀함수가 자기 자신을 부를 때 스택 영역(메모리 영역)에 계속 누적이 됨
2. 일부 컴파일 환경에서는 스택 영역의 메모리가 1MB로 제한되어 있다.
3. 따라서 이 제한이 있는 컴파일 환경에서 재귀가 깊게 들어가는 풀이라면 재귀 대신에 반복문으로 풀어야 한다.
4. 스택 영역에는 지역 변수도 들어간다.