Brute force

재귀호출

단순히 중첩문을 반복하는 것에 비해 코드 수정이 용이해서 재활용 가능성이 높다.

재귀 함수의 종료를 위해 기저 사례를 선택해야한다. 재귀 함수가 가장 깊숙한 곳으로 들어간 경우, 재귀 함수의 목적을 달성한 경우, 반드시 지켜야 하는 특정 조건을 위배한 경우 더 이상 함수가 호출될 필요가 없기 때문에 함수가 반환되도록 해주는 것이다.

재귀 함수의 구현을 위해 어떤 입력 집합, 즉 재귀 함수에 어떤 입력이 들어가야 하는 지를 판단해야 한다.

일반적으로 모든 재귀함수들이 공유해야 하는 전체 수행 회수를 나타내는 변수와 각 재귀함수들의 현재 상태를 나타내는 변수를 입력 집합으로 받는다.

재귀호출을 활용한 완전탐색 문제 접근법

• 완전 탐색은 모든 경우를 탐색하므로 최대크기의 입력에 대해 생성되는 답의 개수를 계산하고, 이것이 제한 시간을 초과하는 지를 확인
• 답을 만드는 과정을 여러 선택으로 나눔
• 하나의 조각을 선택하고 나머지 부분은 재귀 호출하는 함수를 작성
• 기저 사례 설정

재귀호출과 부분문제

재귀 호출은 하나의 문제를 여러 조각으로 나누는 데서 출발한다. 이 때 문제의 한 조각을 해결한 후 나머지 조각을 해결할 때, 원래 문제와 같은 형식의 문제가 반복될 경우 재귀 호출로 접근한다.

최적화 문제