### 17Recursion 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.1Recursive 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 recursive data, such as lists and trees, to our language is quite straightforward. We mainly require two things:
1. The ability to create compound structures (such as nodes that have references to children).

2. The ability to bottom-out the recursion (such as leaves).

Exercise

Add lists and binary trees as built-in datatypes to the programming language.

Adding cyclic data is more subtle. Consider the simplest form of cyclic datum, a cell referring back to itself: Let’s now try to create a cyclic datum. First, let’s see whether we can do it in the language we’re interpreting:
 (let b b b)
This doesn’t work at all: we get an error due to an unbound identifier. It’s easy to see if we desugar it:
 ((lambda (b) b) b)
and, for clarity, we can rename the b in the function:
 ((lambda (x) x) b)
Now it’s patently clear that b is unbound.

Writing something similar in Pyret has a slightly different outcome, but still not the desired one:
<mk-cycle-see-placeholder> ::=
 fun mk-cycle(): b = b b end
The value bound by mk-cycle is a dummy initial value, not a cyclic reference. We will return to this soon: Premature Observation.

In fact, Pyret has a magical construct, graphbased on Racket’s sharedthat 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.

Our plan is as follows. First, we want to create a box and bind it to some identifier, say b. Now, we want to mutate the content of the box. What do we want it to contain? A reference to itself. How does it obtain that reference? By using the name, b, that is already bound to the box. In this way, the mutation creates the cycle:
 fun mk-cycle(): b = box("dummy") b!{v: b} b end
Later [REF] we will study the implications of typing such a program.

Exercise

Run the equivalent program through your interpreter for boxes and make sure it produces a cyclic value. How do you check this?

Exercise

Why did we use a box (or any other mutable structure), above? Why didn’t we use a variable instead?

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.2Recursive 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.

Let’s now try to write a recursive factorial:
 (let fact (lambda (n) (if0 n 1 (* n (fact (+ n -1))))) (fact 10))
But this doesn’t work at all! The inner fact gives an unbound identifier error, just as in our cyclic datum example.

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.

The means to do so is now clear: the problem is the same one we diagnosed before, so we can reuse its solution. We again have to follow a three-step process: first create a placeholder, then refer to the placeholder where we want the cyclic reference, and finally mutate the placeholder before use. Thus:
 (let fact (box -1) (let fact-fun (lambda (n) (if (zero? n) 1 (* n ((unbox fact) (+ n -1))))) (begin (setbox fact fact-fun) ((unbox fact) 10))))
In fact, we don’t even need fact-fun: I’ve used that binding just for clarity. Observe that because it isn’t recursive, its use can simply be substituted with its value:
 (let fact (box -1) (begin (setbox fact (lambda (n) (if (zero? n) 1 (* n ((unbox fact) (+ n -1)))))) ((unbox fact) 10)))
There is the small nuisance of having to repeatedly unbox fact. In a language with variables, this would be even more seamless:Indeed, one use for variables is that they simplify the desguaring of the above pattern, instead of requiring every use of a cyclically-bound identifier to be unboxed. On the other hand, with a little extra effort the desugaring process could take care of doing the unboxing, too.
 (let fact -1 (begin (set fact (lambda (n) (if (zero? n) 1 (* n (fact (+ n -1)))))) (fact 10)))

#### 17.3Syntactic Sugar for Recursive Function Definitions

Our preceding discussion of this pattern shows a clear temporal sequencing: create, update, use. We can capture it in a desugaring rule. Suppose we add the following new syntax:
 (rec name value body)
As an example of its use,
 (rec fact (lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))) (fact 10))
would evaluate to the factorial of 10. To define this syntactic sugar, it is convenient to use variables rather than boxes: that way the body of the bound function would not need to be transformed to replace the bound named (fact, above) with unboxed references to it. Instead,
 (rec name value body)
would desugar to
 (let name -1 (begin (set name value) body))

#### 17.4Premature 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.

There are generally three solutions to this problem:
1. Make sure the value is sufficiently obscure so that it can never be used in a meaningful context. This means values like 0 are especially bad, and indeed most common datatypes should be shunned. Instead, the language might create a new type of value just for use here. Passed to any other operation, this will result in an error.

2. Explicitly check every use of an identifier for belonging to this special “premature” value. While this is technically feasible, it imposes an enormous performance penalty on a program. Thus, it is usually only employed in teaching languages.

3. Allow the recursion constructor to be used only in the case of binding functions, and then make sure that the right-hand side of the binding is syntactically a function. This solution might preclude some reasonable programs.

#### 17.5Recursion 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.

Do Now!

You’ve already seen what goes wrong when we try to use just let to define a recursive function. Try harder. Hint: Substitute more. And then some more. And more!

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.

Exercise

Does the above solution use state anywhere? Implicitly?