Once Upon an Algorithm

by Martin Erwig

  Unbounded recursion can also be found in music, as in never-ending songs (“99 bottles of beer on the wall” and the like) or the drawings of M. C. Escher, such as “Drawing Hands” and “Print Gallery.”6 The work “Drawing Hands” shows one hand drawing a second hand, which in turn draws the first hand. There is no base case, and the recursion does not end. Similarly, “Print Gallery” displays a nonterminating recursion. It is the picture of a town with a gallery in which a man looks at a picture of that same town that includes him in the gallery looking at the picture.

  The two Escher drawings illustrate the difference between direct and indirect recursion. In “Drawing Hands” the recursion is indirect, since instead of drawing itself, each hand draws a different hand—the one by which it is drawn. In contrast, the “Print Gallery” picture contains itself directly, since it immediately shows the town with the print gallery in which that man looks at the picture. “Drawing Hands” also demonstrates that indirect recursion does not guarantee termination. This situation is similar to that for base cases: they are required for termination but are no guarantee for it.

  A popular example of indirect recursion is the definition of the algorithms Even and Odd to determine whether a number is divisible by 2. The definition of Even says that 0 is an even number and any other number is even if its predecessor is odd. In the second equation the definition of Even refers to the algorithm Odd. The definition of Odd says that 0 is not an odd number and any other number is odd if its predecessor is even. In the second equation the definition of Odd refers to the algorithm Even.

  Even(0) = true Odd(0) = false

  Even(n) = Odd(n − 1) Odd(n) = Even(n − 1)

  Thus, Even refers recursively to itself indirectly through the reference to Odd (and vice versa). This can be seen when evaluating a simple example:

  Even(2) = Odd(2 − 1) = Odd(1) = Even(1 − 1) = Even(0) = true

  We see that the call Even(2) is reduced to the call Even(0), but only indirectly via Odd. The definitions of Even and Odd are similar to “Drawing Hands” in that each one defines the other. An important difference, however, is that the recursion in the algorithms is bounded (any computation will terminate with one of the base cases),7 whereas the recursion in the painting is unbounded.

  Another example of direct recursion is the following dictionary-style definition of recursion:8

  Recursion [n], see Recursion.

  This tongue-in-cheek definition incorporates several essential components of recursive definitions, in particular, the use of what is being defined in its own definition and the fact that this is accomplished with the help of a name. The nontermination and empty meaning of this “definition” also captures the uncanny sensation that recursive definitions sometimes evoke. Chapter 13 presents two methods for unraveling recursive definitions and making sense of them.

  State of the Art

  You are done with your work for the day and get back home. Before dinner you have some time to work on your latest sewing project. The quilting pattern you have chosen details the different fabrics and how much of them you need. Since you started the project a few weeks ago, you have bought the fabrics, cut and ironed most of the pieces, and have already begun to sew together some of the quilt blocks.

  The quilting pattern with its associated instructions is an algorithm. Since making a quilt is a lot of work and typically can’t be finished in one session, the execution of the algorithm must be repeatedly interrupted and continued at a later time. Despite the care and attention it takes to make a quilt, it is surprisingly easy to interrupt quilting and pick it up again at a later time, because the state of the quilting process is perfectly represented at each stage by its current results. If you don’t have the fabrics, the next thing to do is buy the fabrics; if you have all the fabrics but don’t have the pieces yet, you have to cut the fabrics next; and so on. The situation is similar for other crafting projects, such as building a birdhouse or folding an origami figure, but there are some tasks that require extra effort to represent the state of computation. Suppose, for example, that you are counting the number of baseball cards in a box of collectibles, and you are interrupted by a phone call. In order to continue the counting, you have to make sure to separate the counted items from the yet-to-be-counted ones and to remember the number of items counted so far.

  In addition to supporting the interruption of work, intermediate results can serve as an explanation of the computation produced by an algorithm, since they keep track of computational steps and provide a trace of what has been done so far. A trace is given by a sequence of computation states that starts with a simple item (for example, a collection of fabrics in quilting, or a plain sheet of paper in origami) and then contains increasingly more accurate approximations of the final result. Each of the approximations is obtained from a preceding one by performing changes to it as described by the algorithm that defines the computation. The sequence of the initial item, all intermediate steps, and the final result is the trace of the computation. And just as a trace of footsteps in the sand explains the movement of a person and how they got from one place to another, the trace of a computation explains the process of how the initial item was transformed into the final result.

  Building a trace is also an effective approach to understanding a recursive description. Even though most quilting patterns are not recursive, we can find some fascinating recursive designs, for example, those that employ Sierpinski triangles. The quilt illustrates nicely the recursion on which it is based. An upright triangle is built of three mostly light-colored upright triangles that enclose one upside-down dark-colored triangle; and an upside-down triangle consists of three upside-down triangles enclosing one upright triangle. Each of the smaller upright triangles is again composed out of three smaller upright triangles enclosing an upside-down triangle, and so on. Note the similarity to the indirect recursion in Escher’s “Drawing Hands” and the Even and Odd algorithms (see chapter 12).

  There are different kinds of traces. In some cases, the algorithm is completely separated from the trace. For example, many assembly descriptions contain numbered steps that describe what to do and then have a separate, correspondingly numbered sequence of pictures that show what the results of the steps are. But there are also traces that consist of pictures containing instructions directly. Both kinds of traces have their strengths and shortcomings, especially when it comes to traces for recursive algorithms. One challenge with executing recursive algorithms is to keep track of all the different executions and their different parameters. For example, the execution of Count(B→W→H) leads to three more executions of Count, all with different lists as parameters. The approach that keeps instructions as part of traces does this very well and without any additional help. The individual steps of the trace are the only representations of the computation and contain all relevant information to continue the computation. However, instructions within a trace can be confusing, and this method can also lead to huge traces, full of redundancy and containing too many snapshots. In contrast, the approach that keeps instructions separate from traces has to manage the correspondence between algorithm and trace but can produce more succinct traces.

  The meaning of an algorithm is given by the set of all computations it can produce.1 Traces make computations concrete and therefore contribute to the understanding of algorithms. Methods for producing traces are thus important tools for elucidating the relationship between algorithms and their computations.

  13

  A Matter of Interpretation

  The focus of chapter 12 was on explaining what recursion is, the different forms of recursion, and how recursion is related to loops. The executions of the algorithms ToDo and Count demonstrated that the execution of descriptive recursion yields unfolded recursion, revealing that the connection between self-reference and self-similarity is computation. However, we have not yet looked in detail at how recursive computation works.

  This chapter illustrates how recursive algorithm
s can be executed. One intriguing aspect is that the execution of an algorithm leads, through recursion, to many executions of the same algorithm. The dynamic behavior of recursive algorithms can be illustrated in two ways.

  First, the use of substitution allows the construction of computation traces out of recursive definitions. The substitution of an argument for a parameter is a fundamental activity that is invoked whenever we execute an algorithm. For executing a recursive algorithm, substitution additionally is employed to replace the call of an algorithm by its definition. In this way, substitution can eliminate descriptive recursion and transform it into a trace that can serve as an explanation of a recursive algorithm.

  Second, the notion of an interpreter provides an alternative approach to explaining recursive algorithms. An interpreter is a specific kind of computer that executes algorithms using a stack data type (see chapter 4) to keep track of recursive (and nonrecursive) calls and multiple copies of arguments that arise as a consequence of recursive algorithm executions. The operation of an interpreter is more complicated than substitution, but it provides an alternative perspective on the execution of recursive algorithms. Moreover, an interpreter can produce traces of computations that are simpler than the substitution-generated ones because they contain only data and no instructions. In addition to explaining how recursion works, these two models help explain one further aspect of recursion, the difference between linear and nonlinear recursion.

  Rewriting History

  An algorithm as a tool for solving problems is of interest only if it can solve a number of related problems (see chapter 2). If a specific algorithm could solve only one problem, such as finding the shortest route from your home to work, you could execute the algorithm once and then remember the route and forget the algorithm. If, on the other hand, the algorithm is parameterized and can find shortest routes between different places of interest, it becomes very useful, since it is applicable in many situations.

  When an algorithm is executed, the resulting computation works on input values that are substituted for the parameters. The getting-up algorithm in chapter 2 consists of the instruction “Wake up at wake-up-time.” To execute that algorithm, a concrete time value such as 6:30 a.m. must be supplied (for example, by setting the alarm), and so the instruction becomes “Wake up at 6:30 a.m.,” obtained by substituting the value 6:30 a.m. for the parameter wake-up-time in the algorithm.

  The substitution mechanism applies to all algorithms and their parameters: cups of water for making coffee, pebbles for finding a path, weather conditions for weather reports, and so on. Of course, parameter substitution also applies to recursive algorithms. For example, quicksort and mergesort require the list that is to be sorted as input; binary search has two parameters, the item to be found and the data structure (tree or array) to perform the search in; and the algorithm Count (see chapter 12) takes the list to be counted as input for its parameter.

  In addition, another kind of substitution is at play in the execution of recursive algorithms, namely, the substitution of the definition of an algorithm for its name, for instance, in the demonstration of how Count computes the number of items Marty took with him on his trip to 1885. Let’s take another look at the equation that defines what the Count algorithm does for nonempty lists:

  Count(x→rest) = Count(rest) + 1

  First, there is the substitution of the argument list for the parameter. Executing Count on the list B→W→H means to substitute the list for the parameter of Count. Since the parameter of Count is represented in the equation as a pattern that consists of two parts, the process of matching the list against this pattern produces two substitutions, B for x and W→H for rest. The substitution affects the right-hand side of the equation, which defines the steps of the algorithm—in this case the execution of the algorithm Count on rest and the addition of 1 to the resulting number. This leads to the following equation:

  Count(B→W→H) = Count(W→H) + 1

  This equation can be understood as the definition of the algorithm instantiated for a particular example case, but it can also be viewed as a substitution of the call of the algorithm by its definition.

  This becomes clearer if we employ the notation for derivations first mentioned in chapter 8. As you may recall, an arrow was used to indicate how a nonterminal grammar symbol is expanded by its defining right-hand side. A sequence of such expansions can be used to derive a string or syntax tree using the grammar rules for a language. We can view the defining equations of a recursive algorithm in the same way as rules for deriving a computation. Using the arrow notation we can rewrite the preceding equation as follows:

  The arrow notation emphasizes that Count(W→H) + 1 is the result of replacing, or substituting, the call of the algorithm Count by its definition. The label Count2 above the arrow indicates that we have used the second equation for Count to do that. Since the result contains a call of Count, we can apply this strategy again and substitute its definition for it, making sure to also substitute the new argument list W→H for the parameter. Again, we have to use the second equation, since the argument list is not empty:

  This last step shows that substitutions generally happen within a context that is unaffected by the substitution. In other words, the substitution replaces a part of a bigger expression and makes a change only locally. This is very much like replacing a light bulb. The old light bulb is removed, and in its place a new one is inserted, leaving the lamp and other parts of the environment unchanged. In the example, the substitution of Count(H) + 1 for Count(W→H) occurs in the context of “+ 1.” We need two more substitution steps to complete the expansion and remove all recursive occurrences of Count:

  Figure 13.1 Recursive picture definition. A name is given to a picture, which contains the name and thus a reference to itself. The meaning of such a self-referential definition can be obtained by repeatedly substituting a scaled-down copy of the picture for its name, thus producing step-by-step an unfolded recursion.

  Note that the last substitution step employs the first rule for Count, which applies to the empty list. Now that we have eliminated all recursion and obtained an arithmetic expression, we can evaluate it and obtain the result.

  We can apply the same strategy to the algorithms ToDo and Goal and use substitution to trace the execution of a recursive time-traveling algorithm, producing a sequence of actions:

  These examples show how the potentially mystifying self-reference in descriptive recursion can be resolved by the repeated substitution of a name by its definition. The repeated substitution of definitions works even for the recursive picture that shows a room containing a TV showing a picture of that room (see figure 13.1).

  Here are the first few steps that show how repeated substitution transforms the descriptive recursion into an unfolded one:

  Of course, this substitution process doesn’t end, since the recursion is unbounded and has no base case. This situation is similar to the definition of the infinite list of 1s:

  Ones = 1→Ones

  When executing this definition, substitution will produce an ever-growing list. In each step, another 1 is added to the list:

  The process of repeatedly substituting names by definitions is also called rewriting, so when we view Marty’s time travels as computations, he is indeed rewriting history.

  A Smaller Footprint

  Substitution is a simple mechanism for producing a trace of a computation, which is basically a sequence of snapshots of intermediate results or states. It works for nonrecursive and recursive algorithms alike, but it is particularly useful for recursive algorithms because it eliminates self-reference and systematically turns a descriptive recursion into a corresponding unfolded one. When we are only interested in the result of a computation and not in the intermediate steps, substitution is doing more than is needed, but the value of a substitution trace lies in its ability to provide an explanation of the computation that has taken place. The Count trace provides such an example.

&
nbsp; However, while a substitution trace can be illuminating, it can also be distracting when it gets too large. Consider again the insertion sort algorithm (see chapter 6). Here is a recursive definition of the algorithm Isort, which uses two lists, the list of elements still to be sorted and the list of elements already in sorted order:

  Isort( , list) = list

  Isort(x→rest, list) = Isort(rest, Insert(x, list))

  Insert(w, )

  = w

  Insert(w, x→rest) = if w ≤ x then w→x→rest else x→Insert(w, rest)

  Figure 13.2 Substitution trace for the execution of insertion sort.

  The algorithm Isort has two arguments. It traverses its first list and executes the auxiliary algorithm Insert for each element of the list. If the list of elements to be sorted is empty, no more sorting is needed, and the second parameter, list, contains the final result. Otherwise, the algorithm Insert moves an element w from the unsorted list to the correct position in the sorted list. If that list is empty, w alone constitutes the resulting sorted list. Otherwise, Insert compares w with the first element (x) of the list into which it is to be inserted. If w is smaller than or equal to x, the correct position has been found, and w is placed at the beginning of the list. Otherwise, Insert keeps x in place and tries to insert w into the remaining list rest. Of course, this works only if the list into which it is to be inserted is itself already sorted, which is indeed the case because that list is built exclusively using the Insert algorithm.