Java Reference

In-Depth Information

We generalize to the task of tiling a
2
n
by
2
n
square, in which one square is

already covered. This is for some
n≥0
:

/**
Tile the
2
n
by
2
n
square with upper left corner
(x,y)
. One

square foot of it is already covered.
*/

public static void
tile(
int
n,
int
x,
int
y)

We develop a recursive procedure to tile the kitchen. Part of our resulting

program is in English, rather than Java, so that we can hide unimportant details.

For example, we are not explicit about where the refrigerator is. This way, the

beautiful idea behind the tiling is most easily seen.

We take
n=0
as the base case. Since
2
0
=1
, a
1
by
1
square has to be tiled.

But it is already covered, so no tiling needs to be done.

We want to solve the case
n>0
using recursion. That requires finding the

same problem on a smaller scale, and the obvious thing to consider is a
2
n-1
by

2
n-1
kitchen. The way to get such a kitchen is to split the
2
n
by
2
n
kitchen into

four quadrants, but then we have four
2
n-1
by
2
n-1
kitchens. One of them con-

tains a covered square, but the other three do not. But we can place one tile so

that it covers one square of each of these three quadrants (see the diagram on the

right in Fig. 15.4). Now, all four quadrants can be tiled using recursive calls to

procedure
tile
. The procedure is given in Fig. 15.5.

Isn't it a neat algorithm? And the key to its development was so simple. In

the recursive case, consciously look for the same problem on a smaller scale.

See lesson

page 15.3 to

get the method

from the CD.

Computing x
y

We develop a recursive function that computes
x
y
for
y≥0
:

/** = x
y
. Precondition:
y≥ 0 */

public static int
exp(
int
x,
int
y)

If
y=0
, then
x
y
=1
, so we use
y=0
as the base case.

15.2.2

Activity

15-3.2

/**
Tile the
2
n
by
2
n
square with upper left corner
(x, y)
.

One sub-square is already covered.
*/

public static void
tile(
int
n,
int
x,
int
y) {

if
(n == 0)

{
return
; }

Place a tile so that each quadrant has one covered square
;

tile(n - 1, x, y);

tile(n - 1, x + 2
n-1
, y);

tile(n - 1, x, y + 2
n-1
);

tile(n - 1, x + 2
n-1
, y + 2
n-1
);

}

Figure 15.5:

Tiling Elaine's kitchen

Search WWH ::

Custom Search