Source code online books for professionals by professionals

Figure 4-3.  Induction (on the left) and recursion (on the right), as mirror images of each other

---

Chapter 4 
■
 InduCtIon and reCursIon ... and reduCtIon 
73
although the recursive algorithm is simple, there is some bookkeeping to do. each call needs to know which 
subboard it’s working on and the number (or label) of the current L-tile. the main work in the function is checking 
which of the four center squares to cover with the L-tile. We cover only the three that don’t correspond to a missing 
(outer) corner. Finally, there are four recursive calls, one for each of the four subproblems. (the next available label 
is returned, so it can be used in the next recursive call.) here’s an example of how you might run the code:
 
>>> board = [[0]*8 for i in range(8)] # Eight by eight checkerboard
>>> board[7][7] = -1                  # Missing corner
>>> cover(board)
22
>>> for row in board:
...     print((" %2i"*8) % tuple(row))
  3  3  4  4  8  8  9  9
  3  2  2  4  8  7  7  9
  5  2  6  6 10 10  7 11
  5  5  6  1  1 10 11 11
 13 13 14  1 18 18 19 19
 13 12 14 14 18 17 17 19
 15 12 12 16 20 17 21 21
 15 15 16 16 20 20 21 -1
 
as you can see, all the numerical labels form L-shapes (except for -1, which represents the missing corner). the 
code can be a bit hard to understand, but imagine understanding it, not to mention designing it, without a basic 
knowledge of induction or recursion!
Induction and recursion go hand in hand in that it is often possible to directly implement an inductive idea 
recursively. However, there are several reasons why an iterative implementation may be superior. There is usually less 
overhead with using a loop than with recursion (so it can be faster), and in most languages (Python included), there is 
a limit to how deep the recursion can go (the maximum stack depth). Take the following example, which just traverses 
a sequence:
 
>>> def trav(seq, i=0):
...     if i==len(seq): return
...     trav(seq, i+1)
...
>>> trav(range(100))
>>> 
 
It works, but try running it on range(1000). You’ll get a RuntimeError complaining that you’ve exceeded the 
maximum recursion depth.
Note
 
■
  Many so-called functional programming languages implement something called tail recursion optimization. 
Functions like the previous (where the only recursive call is the last statement of a function) are modified so that they 
don’t exhaust the stack. typically, the recursive calls are rewritten to loops internally.
Luckily, any recursive function can be rewritten into an iterative one, and vice versa. In some cases, recursion 
is very natural, though, and you may need to fake it in your iterative program, using a stack of your own (as in 
nonrecursive depth-first search, explained in Chapter 5).

---

Chapter 4 
■
 InduCtIon and reCursIon ... and reduCtIon 
74
Let’s look at a couple of basic algorithms where the algorithmic idea can be easily understood by thinking 
recursively but where the implementation lends itself well to iteration.
7
 Consider the problem of sorting (a favorite 
in teaching computer science). As before, ask yourself, where’s the reduction? There are many ways of reducing 
this problem (in Chapter 6 we’ll be reducing it by half), but consider the case where we reduce the problem by one 
element. Either we can assume (inductively) that the first n–1 elements are already sorted and insert element n in the 
right place, or we can find the largest element, place it at position n, and then sort the remaining elements recursively. 
The former gives us insertion sort, while the latter gives selection sort.
Note
 
■
  these algorithms aren’t all that useful, but they’re commonly taught because they serve as excellent examples. 
also, they’re classics, so any algorist should know how they work.
Take a look at the recursive insertion sort in Listing 4-1. It neatly encapsulates the algorithmic idea. To get the 
sequence sorted up to position i, first sort it recursively up to position i–1 (correct by the induction hypothesis) and 
then swap element seq[i] down until it reaches its correct position among the already sorted elements. The base 
case is when i = 0; a single element is trivially sorted. If you wanted, you could add a default case, where i is set 
to len(seq)-1. As explained, even though this implementation lets us encapsulate the induction hypothesis in a 
recursive call, it has practical limitations (for example, in the length of the sequence it’ll work on).