앞서 정의한 상태, 종료 조건, 점화식을 모두 종합하면 다음과 같이 재귀를 정의할 수 있습니다.
▼ 표 5-2 쿼드압축 후 개수 세기 문제의 재귀 정의
|
상태 |
(offsetX, offsetY, size) |
좌표 (offsetX, offsetY)에서 시작하여 가로 길이와 세로 길이가 size인 정사각형을 압축했을 때 남아 있는 0과 1의 개수 |
|
종료 조건 |
|
|
|
점화식 |
(offsetX, offsetY, size) = (offsetX, offsetY, size/2) + (offsetX + size/2, offsetY, size/2) + (offsetX, offsetY + size/2, size/2) + (offsetX + size/2, offsetY + size/2, size/2) |
|
코드 작성
앞서 정의한 재귀를 토대로 코드를 작성해봅시다. 가장 먼저 재귀로 풀어야 하는 부분 문제를 나타내는 상태를 살펴봅시다. 상태를 어떻게 정의했는지에 따라 재귀 메서드의 반환형을 정할 수 있습니다. 하나의 재귀에서는 해당 상태가 나타내는 정사각형을 압축했을 때 남아 있는 0과 1의 개수를 구해야 합니다. 이를 위해 다음과 같이 0과 1의 개수를 한 번에 담을 수 있는 Count 클래스를 작성합니다.