이처럼 하나의 정사각형을 압축하려면 4개의 작은 정사각형으로 나누고, 각 정사각형을 압축한 결과를 모두 더하면 됩니다. 상태 (offsetX, offsetY, size)를 해결하는 점화식을 세워 봅시다.

현재 상태가 나타내는 정사각형 한 변의 길이가 size이므로 작은 부분 문제에서 해결해야 하는 정사각형 한 변의 길이는 size/2입니다. 나누어진 정사각형의 시작 위치 또한 x, y 좌표를 size/2만큼씩 이동하면 다음 그림과 같이 구할 수 있습니다.

▲ 그림 5-5 작은 정사각형들의 시작 좌표

이를 이용하면 점화식은 다음과 같이 정의할 수 있습니다.

(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)