### 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—

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

The ability to create compound structures (such as nodes that have references to children).

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

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 b b |

b) |

((lambda (b) |

b) |

b) |

((lambda (x) |

x) |

b) |

fun mk-cycle(): |

b = b |

b |

end |

In fact, Pyret has a magical construct, graph—

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”—

fun mk-cycle():

b = box("dummy")

b!{v: b}

b

end

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

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

(let fact (lambda (n) |

(if0 n |

1 |

(* n (fact (+ n -1))))) |

(fact 10)) |

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—

(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)))) |

(let fact (box -1) |

(begin |

(setbox fact |

(lambda (n) |

(if (zero? n) |

1 |

(* n ((unbox fact) (+ n -1)))))) |

((unbox fact) 10))) |

(let fact -1 |

(begin |

(set fact |

(lambda (n) |

(if (zero? n) |

1 |

(* n (fact (+ n -1)))))) |

(fact 10))) |

#### 17.3` `Syntactic Sugar for Recursive Function Definitions

(rec name value body) |

(rec fact |

(lambda (n) (if (= n 0) 1 (* n (fact (- n 1))))) |

(fact 10)) |

(rec name value body) |

(let name -1 |

(begin |

(set name value) |

body)) |

#### 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—

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.

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.

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

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.

Does the above solution use state anywhere? Implicitly?