분할정복(Divide-and-Conquer)
분할정복전략은 다음과 같이 동작한다.
- 가장 간단한 경우로 기본 단계를 찾는다.
- 주어진 문제를 작게 줄여서 기본 단계가 되도록 만드는 법을 찾아낸다.
<예시> 배열의 모든 원소를 합하는 sum함수를 재귀를 사용하여 만들기
기본 단계 찾기: 원소가 하나이거나 원소가 없을 때에 sum을 구하는 것은 매우 간단하다.
sum([7]); // prints 7 sum([]); // prints 0그러므로 원소가 하나이거나 없을 때의 합계를 구하는 것이 기본 단계가 된다.
주어진 문제를 작게 줄여서 기본 단계가 되도록 하기
sum([2,4,6])은 2 + sum([4,6]) 과 같다. sum([4,6])은 4 + sum([6])과 같다. sum([6])은 6이다. // 기본 단계즉 sum함수는 다음과 같이 동작한다.
리스트를 받는다. 만약 리스트가 비어 있으면 0을 반환한다. 그렇지 않으면 총합은 리스트의 첫 번째 숫자와 나머지 리스트의 총합을 더한 값이 된다.배열을 포함하는 재귀 함수를 만들 때에 기본 단계는 보통 빈 배열이나 원소가 하나 뿐인 배열이 된다.
그리고 재귀는 상태를 추적하므로 부분적으로 실행된 함수 호출 상태를 모두 저장한다는 점을 기억해야 한다.