Source code online books for professionals by professionals

Figure 4-2.  An incomplete checkerboard, to be covered by L-shaped tiles. The tiles may be rotated, but they may not overlap
1
This is actually Exercise 2-10, but you can still have a go at that, if you want. Try to solve it without using induction.
2
Actually, the solution idea presented in the following will work for a checkerboard where an arbitrary square is missing.  
I recommend you verify that for yourself.

---

Chapter 4 
■
 InduCtIon and reCursIon ... and reduCtIon 
71
Placing a single tile and assuming that we can solve the rest or assuming that we’ve solved all but one and then 
placing the last one—that’s certainly a reduction. We’ve transformed the problem from one to another, but the catch 
is that we have no solution for the new problem either, so it doesn’t really help. To use induction (or recursion), the 
reduction must (generally) be between instances of the same problem of different sizes. For the moment, our problem 
is defined only for the specific board in Figure 
4-2
, but generalizing it to other sizes shouldn’t be too problematic. 
Given this generalization, do you see any useful reductions?
The question is how we can carve up the board into smaller ones of the same shape. It’s quadratic, so a natural 
starting point might be to split it into four smaller squares. The only thing standing between us and a complete 
solution at that point is that only one of the four board parts has the same shape as the original, with the missing 
corner. The other three are complete (quarter-size) checkerboards. That’s easily remedied, however. Just place a 
single tile so that it covers one corner from each of these three subboards, and, as if by magic, we now have four 
subproblems, each equivalent to (but smaller than) the full problem!
To clarify the induction here, let’s say you don’t actually place the tile quite yet. You just note which three corners to 
leave open. By the inductive hypothesis, you can cover the three subboards (with the base case being four-square boards), 
and once you’ve finished, there will be three squares left to cover, in an L-shape.
3
 The inductive step is then to place this 
piece, implicitly combining the four subsolutions. Now, because of induction, we haven’t only solved the problem for the 
eight-by-eight case; the solution holds for any board of this kind, as long as its sides are (equal) powers of two.
Note
 
■
  We haven’t really used induction over all board sizes or all side lengths here. We have implicitly assumed that 
the side lengths are 2k, for some positive integer k, and used induction over k. the result is perfectly valid, but it is  
important to note exactly what we’ve proven. the solution does not hold, for example, for odd-sided boards.
This design was really more of a proof than an actual algorithm. Turning it into an algorithm isn’t all that hard, 
though. You first need to consider all subproblems consisting of four squares, making sure to have their open corners 
properly aligned. Then you combine these into subproblems consisting of 16 squares, still making sure the open 
corners are placed so that they can be joined with L-pieces. Although you can certainly set this up as an iterative 
program with a loop, it turns out to be quite a bit easier with recursion, as you’ll see in the next section.
Mirror, Mirror
In his excellent web video show, Ze Frank once made the following remark: “‘You know there’s nothing to fear but 
fear itself.’ Yeah, that’s called recursion, and that would lead to infinite fear, so thank you.”
4
 Another common piece of 
advice is, “In order to understand recursion, one must first understand recursion.”
Indeed. Recursion can be hard to wrap your head around—although infinite recursion is a rather pathological 
case.
5
 In a way, recursion really makes sense only as a mirror image of induction (see Figure 
4-3
). In induction, we 
(conceptually) start with a base case and show how the inductive step can take us further, up to the full problem 
size, n. For weak induction,
6
 we assume (the inductive hypothesis) that our solution works for n–1, and from that, we 
deduce that it works for n. Recursion usually seems more like breaking things down. You start with a full problem, of 
size n. You delegate the subproblem of size n–1 to a recursive call, wait for the result, and extend the subsolution you 
get to a full solution. I’m sure you can see how this is really just a matter of perspective. In a way, induction shows us 
why recursion works, and recursion gives us an easy way of (directly) implementing our inductive ideas.
3
An important part of this inductive hypothesis is that we can solve the problem no matter which corner is missing.
4
the show with zefrank, February 22, 2007.
5
Ever tried to search for recursion with Google? You might want to try it. And pay attention to the search suggestion.
6
As mentioned in Chapter 3, in weak induction the induction hypothesis applies to n–1, while in strong induction it applies to all 
positive integers k < n.

---

Chapter 4 
■
 InduCtIon and reCursIon ... and reduCtIon 
72
Take the checkerboard problem from the previous section, for example. The easiest way of formulating a solution 
to that (at least in my opinion) is recursive. You place an L-piece so that you get four equivalent subproblems, and 
then you solve them recursively. By induction, the solution will be correct.