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).
Do'stlaringiz bilan baham: 
