Thread: 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.