Welcome to the Java Programming Forums

The professional, friendly Java community. 21,500 members and growing!

The Java Programming Forums are a community of Java programmers from all around the World. Our members have a wide range of skills and they all have one thing in common: A passion to learn and code Java. We invite beginner Java programmers right through to Java professionals to post here and share your knowledge. Become a part of the community, help others, expand your knowledge of Java and enjoy talking with like minded people. Registration is quick and best of all free. We look forward to meeting you.

>> REGISTER NOW TO START POSTING

# Thread: Why does this recursion work for this problem?

1. ## 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.

```    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.  Reply With Quote

3. ## 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.  Reply With Quote