Once Upon an Algorithm

by Martin Erwig

  Note that the time travel analogy might make recursion look more complicated than it really is. When a recursive algorithm is executed by a computer, no timing tricks and fancy scheduling are required. This was evident with binary search in chapter 4 and the quicksort and mergesort algorithms in chapter 6.

  The time travel analogy illustrates two forms of recursion and how they are related. On the one hand, algorithms such as Goal or Count employ recursion in their definitions through self-reference. I call this form of recursion descriptive, since the recursion occurs in the description of the algorithm. On the other hand, when a recursive algorithm is executed, the resulting sequence of similar events or computations comprises instantiations of the recursive description with different values used for the parameters. I call this form of recursion unfolded. As figure 12.1 illustrates, the repeated expansion of recursive algorithm applications transforms a descriptive recursion into an unfolded recursion. In other words, executing a descriptive recursion (that is, a recursive algorithm) yields a corresponding unfolded recursive computation, a view that can be summarized in the following equation:

  Execution(Descriptive Recursion) = Unfolded Recursion

  The recursive picture of the room with a TV showing this room is an example of an unfolded recursion. Given the above relationship, is there a descriptive recursion of it that, when executed, produces it? Yes. One could consider the instructions to take a still image with a video camera of the room and feed the picture into the TV that is located in the room. Carrying out the instructions would produce the unfolded recursive picture.

  In Back to the Future the descriptive recursion is captured in the algorithms ToDo and Goal. In particular, the goals and plans for changing the past are a form of descriptive recursion. And when the plans are executed, the story unfolds into events that are often quite similar to one another, such as the déjà vu cafe/saloon and skateboard/hoverboard scenes.

  It is not only fictional characters in time-traveling movies who formulate goals and plans that contemplate changes in the past. In fact, we all sometimes engage in descriptive recursion by asking, What would have happened if I had done that differently? However, unlike characters in a movie, we cannot execute such plans.

  Fighting Paradoxes with Fixed Points

  Time travel is such an intriguing and entertaining subject in part because it can create paradoxes, impossible situations characterized by logical contradictions that something is and at the same time is not. A well-known example is the grandfather paradox, referring to a time traveler who goes back in time to kill his own grandfather (before the grandfather has conceived the time traveler’s father or mother). This makes the time traveler’s own existence impossible, including his time traveling and the killing of the grandfather. The grandfather paradox has been used to argue that time travel into the past is not possible, since it can lead to such logically impossible situations that contradict our understanding of causality. In Back to the Future II, Doc Brown warns about the possible consequences should Jennifer encounter her future self:

  The encounter could create a time paradox, the results of which could cause a chain reaction that would unravel the very fabric of the space-time continuum, and destroy the entire universe! Granted, that’s a worst-case scenario. The destruction might in fact be very localized, limited to merely our own galaxy.

  One response to the problem of paradoxes is to assume that it’s actually not possible to take actions that will cause a paradox. For example, even if you could travel into the past, it would be impossible for you to kill your grandfather. Concretely, suppose you try to kill your grandfather with a gun. Then maybe you would fail to get hold of a gun, or if you tried to use the gun, it would jam, or your grandfather would dodge the bullet, or even if it hit him, he would only be injured and recover. Maybe the nature of the space-time continuum is such that it permits only actions in the past that are consistent with what is certain to happen in the future.

  Does the equivalent of the grandfather paradox exist in the realm of computation? Yes. For example, any nonterminating execution of a recursive algorithm can be considered such a paradox. In the following I explain this view in more detail, using the concept of a fixed point.

  To produce a paradox, it seems that we need to identify a recursive computation that triggers a trip into the past and changes it so that the triggering computation disappears or becomes impossible. Stopping short of actually going back in time, the closest we can probably get is an algorithm that deletes itself or destroys the computer on which it is running. In such a situation, the execution of the algorithm would simply stop, so there is no real paradox to be resolved in that case. But this example only looks at unfolded recursion. There are many cases of descriptive recursion that are paradoxes. Recall the recursive definition of Count, which was given by an equation that said that the number of elements in a list is obtained by adding 1 to the number of elements in the list’s tail. There is no paradox here, but suppose we changed the definition slightly by applying Count recursively to the whole list and not the list’s tail:

  Count(list) = Count(list) + 1

  This seems to be defining the number of elements as one more than the number of elements, a clear contradiction. A similar example is the following equation, which tries to define a number n that is 1 larger than itself:

  n = n + 1

  Again, this is a contradiction, or paradox, and the equation has no solution. In terms of the time-traveling analogy, the attempt to go back in time to compute a value for n or Count(list) will not terminate and thus can never reach the point where we could add 1. In other words, there is no way that the desired actions in the past can be carried out to be consistent with the action in the present, which amounts to the paradox that the number of elements in a list should be two different values at the same time.

  In reality, apparent paradoxes are often resolved by the constraints of physics. For example, the seemingly infinite recursion in the picture of the room with the TV stops with the resolution of the camera. Once a deeply nested TV picture gets as small as one pixel, the recursion stops and will not present a picture of the room as part of that pixel. Similarly, in the case of audio feedback when the output of an amplifier is input (fed back) to a microphone connected to it, the amplification does not proceed infinitely. The paradox in this case is resolved by the physical limitations of the microphone and amplifier, which are both limited with respect to the amplitude of signals they can handle.

  Chapter 9 discussed the fact that languages have semantics and that the semantics of an algorithm expressed in some programming language is a computation that is carried out when the algorithm is executed. From this perspective, the meaning of algorithms that are contradictory and lead to paradoxes is undefined, that is, there is no computation that would do what the algorithm demands. How can we tell whether a recursive algorithm is contradictory and entails a paradox?

  The example of a recursive number definition can help illuminate the problem. Consider the following equation, which says the number being defined is equal to its own square:

  n = n × n

  This is actually not a contradiction. There are two natural numbers for which the equation is true, namely, 1 and 0. And this is the key to understanding recursive definitions. The defined number is a solution to the equation, that is, it is a number that when substituted for the variable n will yield a true statement and not a contradiction. In the case of this number equation, we obtain, for example, 1 = 1 × 1, which is true, so 1 is a solution for that equation. In contrast, the equation n = n + 1 does not have a solution. Similarly, the equation Count(list) = Count(list) + 1 does not have a solution either, but the original equation does. In that case, it is a computation that computes the number of elements contained in a list.

  An equation that contains the same variable on both sides can be viewed as being defined by a transformation. For example, the equation n = n + 1 says that n is defined by adding 1 to itself, or n =
n × n says that n is defined by multiplying it by itself. Any number n that is unaffected by a transformation is called a fixed point of that transformation. As the name suggests, the value does not change and remains fixed.

  Examples of fixed points that make the term point more fitting arise for geometric transformations. Consider, for example, the rotation of a picture around its center. All points change their position except for the center, which stays at its place. The center is a fixed point of the rotation transformation. In fact, the center is the only fixed point of the rotation. Or consider reflecting a picture along one of its diagonals. In this case all of the points on the diagonal are fixed points of the reflection transformation. Finally, shifting a picture to the left does not have any fixed point, since all points are affected. For the number examples, the “adding 1” transformation has no fixed points, whereas the “multiply by itself” transformation has the two fixed points: 1 and 0.

  What is the transformation that corresponds to the equation defining Count? First, we observe that the changed definition Count(list) = Count(list) + 1 is very similar to the definition n = n + 1 except that it has a parameter. This definition corresponds to the transformation that says Count applied to list is defined by adding 1 to this application. This transformation, like the one for the equation for n, does not have a fixed point. In contrast, the transformation for the original definition Count(x→rest) = Count(rest) + 1 says that Count applied to list is defined by removing the first element of list in that application and then adding 1. This transformation (together with the equation defining the case for the empty list) does have a fixed point, which turns out to be the function that counts the elements in a list.

  The meaning of a recursive equation is the fixed point of its underlying transformation—that is, if such a fixed point exists.3 When the recursive equation describes an algorithm, the fixed point describes a computation that is stable under a transformation that makes it applicable to a large number of cases. The transformation typically adapts the argument of the algorithm, and it might also modify the result of the recursive call. In the case of Count, the argument list has its first element removed, and the result is increased by 1. In the case of Goal, the recursive equations execute Goal with different goals and add other activities that are pertinent to each case.

  Viewed from the time-traveling perspective, the fixed point of a recursive algorithm describes a computation whose effects in the past are consistent with those in the present. This is why fixed points are relevant for recursion. Recursive algorithms, like time travelers, must behave properly and avoid paradoxes to be successful. If a recursive algorithm has a fixed point, it denotes a meaningful computation. Otherwise, it amounts to a paradox. However, unlike time travel paradoxes, it doesn’t destroy the universe; it simply doesn’t compute what you want. Understanding the meaning of a recursive algorithm as a fixed point is not easy. Chapter 13 demonstrates another way of making sense of recursive algorithm descriptions.

  To Loop or Not to Loop

  Recursion is a control structure that is equivalent to loops, that is, any loop in an algorithm can be replaced by recursion, and vice versa. In some examples one or the other feels more natural, but this impression is often due to a bias from prior exposure to either control structure. For example, how could one not view Hansel and Gretel’s pebble-tracing algorithm as a loop?

  Find a pebble not visited before, and go toward it until you are home.

  It clearly is an example of a repeat loop. While this is indeed a clear and simple description of the algorithm, the following equivalent recursive version, FindHomeFrom, is only slightly longer:4

  FindHomeFrom(home) = do nothing

  FindHomeFrom(forest) = FindHomeFrom(next unvisited pebble)

  Like the other recursive algorithms presented here, FindHomeFrom is given by multiple equations that distinguish the different cases to consider by a parameter. In this case, the parameter represents a position from which the algorithm finds the way home, and the two cases are whether the current position of Hansel and Gretel is already home or still in the forest.

  The recursive algorithm is arguably a bit more precise than the loop version, since it terminates in case Hansel and Gretel’s father leads them into their backyard. In that case Hansel would not drop any pebble, since they never left home. However, the loop algorithm instructs them to find a pebble, which would lead to a nonterminating computation. This is not a problem with loops per se, but rather a consequence of using a repeat loop to describe the algorithm where a while loop, “While you are not home, find a pebble not visited before, and go toward it,”; would have been more appropriate because it tests the termination condition before executing the body of the loop.

  The recursive formulation illustrates how a loop can be expressed using recursion. First, the two outcomes of the termination condition (having reached home or still being in the forest) are represented explicitly as parameters of equations. Second, the loop’s body becomes part of the equation whose parameter represents the nonterminating case (here, the position being in the forest). Third, the continuation of the loop is expressed as a recursive execution of the algorithm with an appropriately changed argument (here the position of the next unvisited pebble).

  I have shown a recursive version of the Groundhog Day loop in chapter 10 using a conditional. Using equations and pattern matching we can also express the Groundhog Day loop in the following way:

  GroundhogDay(true) = do nothing

  GroundhogDay(false) = experience the day; GroundhogDay(good person?)

  Compared with the loop repeat experience the day until good person, this seems to be more complicated. But it would be incorrect to conclude that loops are always easier to program with than recursion. Recursion is particularly well suited for problems that can be decomposed into subproblems (see divide-and-conquer algorithms in chapter 6). Recursive algorithms for those problems are often simpler and clearer than their loop-based counterparts. It is an instructive exercise to try to implement an algorithm such as quicksort without recursion to appreciate this point.

  The Many Faces of Recursion

  Recursion is often portrayed as being mysterious and difficult to use, which is regrettable, since such a reputation is undeserved. Much of the confusion about recursion can be resolved by contemplating the different aspects of recursion and how they are related. We can distinguish different forms of recursion according to a number of categories, such as the following:5

  Execution: unfolded vs. descriptive

  Termination: bounded vs. unbounded

  Reach: direct vs. indirect

  I have already discussed the difference between unfolded and descriptive recursion and the way they are related through computation. Recall that the execution of a descriptive recursion produces an unfolded recursion, which can be helpful in making sense of a recursive situation. On the one hand, when confronted with an unfolded recursion, one can try to think of the descriptive recursion which, when executed, would result in the unfolded recursion. The descriptive recursion can often provide a compact characterization of the situation, particularly when the recursion is also unbounded. On the other hand, given a descriptive recursion, it can often be helpful to execute the definition to see the unfolded version, especially in cases when the recursion has a more complicated form, such as when it involves multiple recursive occurrences. For the picture containing the TV example, what would the result be if one added a second camera and a second TV so that the cameras could record each other’s projected picture plus both TV pictures? Seeing how the descriptive recursion produces the unfolded recursion helps with making sense of recursion.

  A bounded recursion is one that terminates. Only for unfolded recursion does it make sense to distinguish between bounded and unbounded recursion. However, we can ask what the requirements for descriptive recursion are to produce bounded recursion. One condition is that the description of the recursion must contain some part that does not itself in
voke recursion, such as the definitions for Goal(save Doc) or Count( ). Such equations are called base cases. While a base case is always required to end the recursion, it is not a guarantee for termination because the recursive case(s) could be such that the base case is never reached. Recall the definition Count(list) = Count(list) + 1, which will never terminate when applied to a nonempty list, even if it has a base case for the empty list.

  Is unbounded recursion useful at all? It would seem that recursive computations that do not terminate could not produce any result and would therefore be meaningless. This may be so if such computations are considered in isolation, but as components of other computations unbounded recursions can be quite useful. Suppose a computation produces an infinite stream of random numbers. Such a stream can be useful for implementing simulations. As long as only a finite portion of the infinite stream is consumed, the computation can behave well and simply ignore the infinite parts. As another example, consider the following definition of an infinite list of 1s, which says that the list has 1 as its first element and is followed by a list of 1s:

  Ones = 1→Ones

  Executing this definition will lead to an infinite sequence of 1s:

  1→1→1→1→1→1→ …

  Like the picture of the room with the TV, this list contains itself as a part. The equation shows this, as does the unfolded list. The infinite list of 1s starts with a 1 and is followed by a list of 1s, which is also infinite.

  This view of self-containment also helps to explain self-similarity as a result of recursion. If we write the list computed by Ones on one line, and the list computed by 1→Ones on the line beneath it, we will see two lists that are absolutely identical. Since both lists are infinite, the one on the second line does not contain an additional element.