[실전 알고리즘] 재귀

재귀

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

 

사고법

절차지향적 사고 X  귀납적 사고 O

ex. '1번 도미노가 쓰러진다', 'k번 도미노가 쓰러지면 k+1번 도미노도 쓰러진다' 까지만 생각한 후에 바로 모든 도미노가 쓰러진다는 결론에 도달할 수 있어야 함

 

 

재귀함수의 조건

특정 입력에 대해서는 자기 자신을 호출하지 않고 종료되어야함(Base condition)

모든 입력은 base condition으로 수렴해야 함

 

 

재귀에 대한 정보

1. 함수를 명확하게 정의 : 함수의 인자로 어떤 것을 받고 어디까지 계산한 후 자기 자신에게 넘겨줄지 명확하게 정해야 함

2. 모든 재귀함수는 반복문만으로 동일한 동작을 하는 함수를 만들 수 있음

3. 재귀는 반복문으로 구현했을 때에 비해 코드가 간결하지마 메모리/시간에서는 손해를 봄

 

 

문제 풀이 접근

1. 함수의 정의

 

2. base condition

 

3. 재귀 식

 

 

 

 

출처

BaaaaaaaarkingDog | [실전 알고리즘] 0x0B강 - 재귀 (encrypted.gg)