分割するという発想じゃなくて
「指定のRECTを含まないRECTを一つ除外する」という処理を
再帰的に指定のRECTと同じサイズになるまで繰り返せばいいんじゃね?