17 Recursion and Cycles

Recursion is the act of self-reference. When we speak of recursion in programming languages, we may have one of (at least) two meanings in mind: recursion in data, and recursion in control (i.e., of program behavior—that is to say, of functions).

17.1 Recursive and Cyclic Data

Recursion in data can refer to one of two things. It can mean referring to something of the same kind, or referring to the same thing itself.

Recursion of the same kind leads to what we traditionally call recursive data. For instance, a tree is a recursive data structure: each vertex can have multiple children, each of which is itself a tree. But if we write a procedure to traverse the nodes of a tree, we expect it to terminate without having to keep track of which nodes it has already visited. They are finite data structures.

In contrast, a graph is often a cyclic datum: a node refers to another node, which may refer back to the original one. (Or, for that matter, a node may refer directly to itself.) When we traverse a graph, absent any explicit checks for what we have already visited, we should expect a computation to diverge, i.e., not terminate. Graph algorithms thus need a memory of what they have visited to avoid repeating traversals.

Adding cyclic data is more subtle. Consider the simplest form of cyclic datum, a cell referring back to itself:

In fact, Pyret has a magical construct, graph—based on Racket’s shared—that enables you to create graphs directly. In Pyret, you only need to declare that the corresponding field of a data definition is potentially cyclic (absent any such a declarations in a data definition, all of its instances are guaranteed to be finite). But so few languages have such a construct that we should not rely on it. Indeed, what we will do below is study how such a construct might be defined.

To create a cyclic reference, then, we must work in two steps. We need to first create a “place” for the datum, then refer to that place within itself. The use of “then”—i.e., the introduction of time—should suggest a mutation operation. Indeed, let’s try it with boxes.

The idea above generalizes to other datatypes. In this same way we can also produce cyclic lists, graphs, and so on. The central idea is this two-step process: first name a vacant placeholder; then mutate the placeholder so its content is itself; to obtain “itself”, use the name previously bound. Of course, we need not be limited to “self-cycles”: we can also have mutually-cyclic data (where no one element is cyclic but their combination is).

17.2 Recursive Functions

In a shift in terminology, a recursive function is not a reference to a same kind of function but rather to the same function itself, i.e., it’s a cyclic function. Before we proceed, it’ll be useful to first ensure we’ve first extended our language with conditionals (even of the kind that only check for 0, as described earlier: Adding Functions to the Language), so we can write non-trivial programs that terminate.

It is no surprise that we should encounter the same error, because it has the same cause. Our traditional binding mechanism does not automatically make function definitions cyclic (indeed, in some early programming languages, recursion was considered a special feature). Instead, if we want recursion—i.e., for a function definition to cyclically refer to itself—we must implement it by hand.

17.3 Syntactic Sugar for Recursive Function Definitions

17.4 Premature Observation

This three-step minuet inspires a natural question: what if we get these out of order? Most interestingly, what if we try to use name before we’re done updating its true value into place? Then we observe the state of the system right after creation, i.e., we can see the placeholder in its raw form.

We have already seen a simple example that illustrates this: <mk-cycle-see-placeholder>. This program leaks the initial value given to the placeholder—a value that was never meant for public consumption. This is troubling because it is, after all, a legitimate value, which means it can probably be used in at least some computations. If a developer accesses and uses it inadvertently, however, they are effectively computing with nonsense.

17.5 Recursion Without Explicit State

As you may be aware, there is another way to define recursive functions (and hence recursive data) that does not leverage explicit mutation operations.

Obtaining recursion from just functions is an amazing idea, and I use the term literally. Until our write-up is in place (Shrinking the Language [EMPTY]), see the excerpt from Daniel P. Friedman and Matthias Felleisen’s book, The Little Schemer. Read about it in their sample chapter online.