개요

• 문제는 작으면 작을수록 해결하기 편함

1. 어떤 문제를 해결할 때는 충분히 해결할 수 있을 정도로 작게 나눈 후 접근하는 것이 일반적

• 재귀를 통해 분할 정복법에 대해 탐구

재귀

• 함수가 자기 자신을 호출하는 것
• 문제에 따라 전체를 한 번에 해결하기 보다 같은유형 하위 작업으로 분할하여 작은 문제부터 해결하는 방법이 효율적일 수 있기 때문에 사용
• 재귀의 구조는 재귀를 중단시키는 기저 조건과 기저 조건으로 수렴하게 되는 재귀 조건으로 구성
• 재귀호출이 바로 분할 정복법

1. 분할 정복법 : 작은 문제들 먼저 해결해 나가며 결과적으로 복잡하고 큰 문제를 해결

• 재귀는 결국 함수를 호출하는 것이므로 함수 호출에 따른 오버헤드가 있음
• 재귀가 너무 깊어지면 호출 스택의 공간을 더 많이 사용하게 되고, 스택 오버플로가 발생할수도 있음

반복문과의 변환

• 모든 반복문은 재귀로 변환할 수 있음

1. 반복 횟수와 관련이 있는 데이터는 전부 매개변수로

• 모든 반복문은 재귀로 변환할 수 있지만, 모든 재귀를 반복문으로 변환할 수는 없음
  
  

재귀를 이용해 10진수를 2진수로 출력해보기

동적 계획법

• 해결했던 문제에 대한 해답을 저장해두고 이후에 다시 활용하는 것
• 재귀에 룩업 테이블을 결합한 형태라고 할 수 있음