재귀

 

 

 

절차지향적인 사고를 버려야 재귀 파트를 이해할 수 있다.

 

재귀함수는 base condition(종료조건)이 있어야 하고, 모든 입력은 base condition으로 수렴해야 한다.

 

재귀함수를 사용하면 반복문을 사용하는 것 보다 효율적이지 않은 경우가 많고, 적절히 dp를 사용하지 않으면 계산했던 결과를 또 계산하는 경우가 많이 생길 수 있어 조심스럽게 사용해야 한다.

 

그럼에도 재귀를 이용하면 굉장히 편하게 작성할 수 있는 경우나, 재귀를 사용해야만 작성할 수 있는 코드들이 있으니 재귀를 포기할 수는 없다.

 

 

a에서 a/2를 호출하고 a가 1에서 return을 만나는 함수가 있다고 해 보자.

a가 1000이면 1000 -> 500 -> 250 -> 125 -> 62 -> 31 -> 15 ..... 이런 방식의 생각은 절차지향적인 생각이다.

 

재귀를 공부할 때는 절차지향의 사고를 잠시 접어 두고, 재귀적 사고를 구축해야 한다.

 

도미노를 쓰러뜨릴 때 첫 번째 도미노가 두 번째 도미노를, 두 번째 도미노가 세 번째 도미노를... 이후 k번째 도미노까지 쓰러짐을 알 수 있다.

 

재귀함수도 이와 비슷한데, base condition을 잘 정의했다면 그 다음 코드는 내가 쓴 코드를 믿고 가야한다.

아 그래 base 설정해뒀으니까 잘 되겠지 뭐.. 라고 의연한 태도를 가져야 한다.

 

다시 한 번 말하지만, 지금까지의 사고를 깨야 한다.

절차지향적인 사고를 붙잡고 있으면 재귀적 사고를 받아들이기 쉽지 않다. 

 

어느 정도 믿고 가는 영역도 있는데, 일단은 많은 연습을 통해 재귀적 사고에 익숙해지고 재귀 스타일의 코드에 익숙해지자.