Data Structures Using C: 4.2.6 Counting Squares

4.2.6 Counting Squares

The third example relates to counting squares. Consider an n ?/FONT> n checkerboard and determine the number of ways a 4 ?/FONT> 4 checkerboard can be placed on it. For example, if n = 5, there are four ways to place a 4 ?/FONT> 4 checkerboard on the 5 ?/FONT> 5 board, as shown below.

For this particular example the solution is easy to see by inspection. However, how do you state an algorithm that produces the result in all cases? This can be done handily using recursion. Suppose you know the number of ways, f(n - 1), in which the 4 ?/FONT> 4 board can be placed on an (n - 1) ?/FONT> (n - 1) board. An additional (n - 3) + (n - 4) placements result from an n ?/FONT> n board, because of the n cells

Figure 4.5 An n x n Checkerboard

added at the top and left sides of the (n - 1) ?/FONT> (n - 1) board, as shown in Figure 4.5. There are a total of f(n) = f(n - 1) + (n - 3) + (n - 4) placements for the n ?/FONT> n board, when n ?/FONT> 5. If n = 4, f(4) = 1. So the following is true.

f(n) is

1 if n = 4

f(n - 1) + (n - 3) + (n - 4) if n ?/FONT> 5

It is easy to write a recursive function f, with parameter n, to return the correct result for any n ?/FONT> 4.

f(n)

int n;

if (n == 4)

return (1);

else

return(f(n-1)+(n-3)+(n-4));

If n = 7, the program would execute as follows:

f(7) = f(6) + (7 - 3) + (7 - 4)

f(6) = f(5) + (6 - 3) + (6 - 4)

f(5) = f(4) + (5 - 3) + (5 - 4)

f(4) = 1

f(5) = 1 + 2 + 1 = 4

f(6) = 4 + 3 + 2 = 9

f(7) = 9 + 4 + 3 = 16

A simpler, more direct solution can be obtained by noticing that the top left corner of the 4 x 4 board can be placed in the first, second, . . . , (n - 3)th position of the top row of the n ?/FONT> n board, resulting in (n - 3) different placements. The second row also allows (n - 3) placements. In fact, each of the first (n - 3) rows allows (n - 3) placements, for a total of (n - 3) ?/FONT> (n - 3) distinct placements.Thus f(n) = (n - 3) ?/FONT> (n - 3) for n ?/FONT> 4. The program for this solution would be

f(n)

int n;

return((n-3)*(n-3));

The recursive solution will take time and storage O(n), whereas the nonrecursive solution requires constant time and storage. Obviously, this solution is better in every way than the recursive solution to this problem. Hence recursion does not always yield the best solution. Just as with any tool, it must be used judiciously. You wouldn't use a bulldozer to dig a two-foot hole in your yard.