Why does this recursion work for this problem?

You are given a rectangular floor that is to be tiled with square tiles. The tiles come in a variety of sizes, but they all measure in some power of two: 1, 2, 4, 8, etc. A 5x6 space can be tiled with 30 of the smallest tile, but the minimum number of tiles required is only 9. Refer to the pattern below.

http://nayuki.eigenstate.org/res/dwi...-201010-p3.png

Find the minimum number of tiles.

Code :

private static int getFloorTileCount(int width, int height) {
if (width == 0 || height == 0) {
return 0;
} else if (width % 2 == 0 && height % 2 == 0) {
return getFloorTileCount(width / 2, height / 2);
} else if (width % 2 == 0 && height % 2 == 1) {
return width + getFloorTileCount(width / 2, height / 2);
} else if (width % 2 == 1 && height % 2 == 0) {
return height + getFloorTileCount(width / 2, height / 2);
}
return width + height - 1 + getFloorTileCount(width / 2, height / 2);
}

I can't seem to understand why this code is able to get the minimum number of tiles required.

Re: Why does this recursion work for this problem?

A normal person doing this problem would prolly figure out what the biggest block is that they could put in the grid and work their way to the smaller tiles. This program is doing the opposite. It starts with determining if any of the smallest tiles are required then divides the grid width and height by 2 (this is equivalent of increasing your grid size). I'll explain that another way. Your grid of 5x6 can fit 5x6 small tiles, but a 4x6 grid could fit 2x3 of the next larger tiles. Make sense? The if statement is trying to determine if the height or width is odd therefore requiring the size tile you are on. If neither is odd, it just increases the size of the tile (by dividing the grid by 2) then calls itself again.

Order of execution for 5x6 grid...

Width is odd so we need 6 (value of height) tiles to make it even

Now increase the size of the tile by dividing the grid: grid now 2x3 (Remember an int of 5 divided by 2 is 2. You drop the remainder)

Height is odd so we need 2 (value of width) tiles to make it even

Now increase the size of the tile by dividing the grid: grid now 1x1

Both are odd so we need 1 tile (width + height -1 => this is basically getting the left and bottom border with tiles but we only need one)

Now we increase the size of the tile by dividing the grid: grid now 0x0

Empty grid now we return and add all the results we've gotten along the way. 1 big tile, 2 medium tiles, 6 small tiles = 9 tiles.