Factorial

Let’s consider two examples of recursive definitions that are more serious than the recursive acronyms. The first example is mathematical; the next one is linguistic. (If you think of yourself as a person who “doesn’t like math,” you may prefer to skip this example and go directly to the following one.)

Our mathematical example is the definition of factorial. The factorial of some positive integer n is the result of multiplying together all the numbers from 1 through n. The factorial of n is written “n!” and so one way to define it would be

n! = 1 × 2 … × (n − 1) × n

This definition takes advantage of our understanding of how a series works and what is meant by the ellipsis “…” to leave out the “middle” terms of the series. We can make this construction a little clearer by distinguishing two different cases:

For n = 1: n! = 1

For n > 1: n! = 1 × … × (n − 1) × n

That is, we’ve split the definition into two cases: the first for the case where n has the value one, and the other for all cases where n is more than one. Let’s consider an alternative formulation using recursion, but retaining the case-analysis framing:

For n = 1: n! = 1

For n > 1: n! = n × (n − 1)!

In contrast to all our previous definitions of factorial, this version uses the factorial sign “!” on the right-hand side of an equals sign. In fact, the second line looks circular: the factorial of n is being defined in terms of another factorial. We can immediately see the risk of infinite expansion here (revisiting the problem we saw with expanding XINU earlier). What are we gaining that makes this useful?

The first line provides one alternative (what computer scientists would call a base case): it ensures that for some simple version of the problem we can provide a compact answer. The second line is another alternative (what computer scientists would call a reduction step): it ensures that we can repeatedly move toward the base case as we compute a partial result. So the recursive definition effectively provides us a means of computing n!: we can repeatedly invoke the definition, as in this example of computing 4!:

4! = 4 × 3!

4! = 4 × (3 × 2!)

4! = 4 × (3 × (2 × 1!))

4! = 4 × (3 × (2 × 1))

4! = 4 × (3 × 2)

4! = 4 × 6

4! = 24

All we’ve done here is repeatedly substitute the definition of factorial until we reach the base case, then simplify.

The House That Jack Built

Now let’s look at a linguistic version of recursion. There’s a Mother Goose tale that is relevant here because it effectively teaches the repeated use of a modifying clause:

This is the house that Jack built.

This is the malt that lay in the house that Jack built.

This is the rat that ate the malt that lay in the house that Jack built.

The story goes on in the same vein, eventually building a sentence involving 11 different noun phrases:

This is the farmer sowing his corn,

That kept the cock that crowed in the morn,

That waked the priest all shaven and shorn,

That married the man all tattered and torn,

That kissed the maiden all forlorn,

That milked the cow with the crumpled horn,

That tossed the dog,

That worried the cat,

That killed the rat,

That ate the malt

That lay in the house that Jack built.

It seems likely that all reasonably intelligent children exposed to this story eventually notice that the same mechanism is used repeatedly and that the ending point is flexible—the tale could plausibly be extended yet again.

If we analyze this story, we can break it down into just a few rules. First there is a kind of frame for the extension:

This is [] the house that Jack built

Here we’re marking with brackets a place where “other stuff” gets inserted while the surrounding frame stays the same. If we look at the things that go in there, we see a pattern:

[]

[the malt that lay in]

[the rat that ate [the malt that lay in]]

[the cat that killed [the rat that ate [the malt that lay in]]]

That might be where we stop if we were thinking conventionally, but if we’re thinking like computer scientists, we would like to design rules that would generate these kinds of phrases.

We can start by saying that one rule is about picking nouns. In the examples just preceding we have only three nouns, so let’s stick with those. Wherever we use a noun, we’ll use “malt” or “rat” or “cat.” We can write that rule like this:

noun = malt | rat | cat

The vertical bar “|” represents a choice or alternative, roughly analogous to the two cases we had in defining the factorial function in the previous example. It’s usually read aloud as “or”—so in this case, the noun could be “malt” or “rat” or “cat.”

Similarly, in our examples above we had only three verbs, so we’ll stick with those. Wherever we use a verb, we’ll use “killed” or “ate” or “lay in.”

verb = killed | ate | lay in

We can then see that nouns and verbs are combined in a particular way that we can call a “that-phrase.” Our examples are “the malt that lay in,” “the rat that ate,” and “the cat that killed” so what we notice is that it’s always “the,” then a noun, then “that,” then a verb:

that-phrase = the noun that verb

To capture the lengthening phrases, we use a recursive definition that lets us nest that-phrases the right way. We can keep adding more that-phrases “bracketing” what we’ve built up, and the overall phrase will still make sense. For example, we already saw

[the cat that killed [the rat that ate [the malt that lay in]]]

and it’s still grammatical (if conceptually strange) if we wrap that in another phrase like this:

[the malt that ate [the cat that killed [the rat that ate [the malt that lay in]]]]

So the scheme here can be summarized by the following rule:

compound-phrase = compound-phrase that-phrase | that-phrase

Notice that compound-phrase is both the thing being defined (on the left-hand side of the equals sign) and part of the definition (on the right-hand side of the equals sign). Why isn’t this a meaningless or silly kind of circularity? We’re OK because there is a nonrecursive alternative. We can stop “choosing” the recursive part and instead pick the part where the compound-phrase is only a that-phrase. We already know that a that-phrase has a nice compact (and nonrecursive) definition.

We saw a similar structure in the factorial definition—there the base case was the situation where n = 1, because in that situation the answer is just 1, not some computation that depends recursively on the definition of factorial. For the phrase generator, the base case is when there’s only a that-phrase and no additional compound-phrase.

If we apply these rules, making random selections each time there is a choice, we can generate some plausible if uninspiring new verses for the Mother Goose tale, like

This is the malt that killed the rat that lay in the cat that lay in the cat that ate the rat that lay in the malt that killed the house that Jack built.

That’s not great literature, but neither is it ungrammatical. Contrast it with a nonsentence like

This is malt rat killed cat cat the house that Jack built

The second one is worse than the first one; while the first one may be silly or meaningless, it’s not incoherent or garbled in the way of the second one. As computer scientists we can demonstrate that lack of coherence by comparing it to the rules we derived. Alternatively, as speakers of English we can notice it intuitively. The simple mechanical rules seem to have something in common with what’s happening in our brains when we are dealing with language, which in turn suggests (but doesn’t prove) that our brains may use some kind of similar rules.

Finite and Infinite

Now let’s return to the question of whether, and how, recursive thinking matters for a nonprogrammer. Recursion arguably underpins the capacity of language to be infinitely generative but finitely comprehensible. That is, we each have only a finite amount of capacity for producing or understanding language. Our brains may be big and complex compared to most other mammals, but they are still definitely finite … and actually quite small when compared to an infinite amount of anything! However, the finite brain doesn’t imply a finite bound on language. Even if we could somehow catalog all of the utterances produced by all humans across all time, we would not have exhausted the possibilities of language because we could add an additional clause in the middle or at the end of one of those cataloged expressions. There seems to be no clear limit to our ability to generate new sentences and embed sentences as clauses in other sentences. The set of words and sentences used by an individual at any instant is finite, but there is nothing that prevents that person from understanding new words and sentences—there is no point at which either the brain “runs out” or the language itself “hits a wall.”

While human language contains many additional features and complexities not captured in such a simple arrangement, it’s nevertheless compelling as a “proof of concept” that a finite apparatus can produce and consume infinitely varied languages. Even if natural languages do not use exactly the same recursion that computer scientists and mathematicians know, the computer-science recursion seems like a handy metaphor.

Recursive thinking is also a problem-solving technique. For example, we can approach a problem with the mindset of looking for a small number of simple base cases and then looking for recursion steps that allow us to decompose bigger problems to the simple cases. Viewed in this light, recursion is a special case of the general principle that one can divide and conquer. In a problem-solving context, the infinite extensibility of recursion means that the sheer size of a problem need not be a limitation. In the same way that we don’t worry about “running out of” language, a recursive formulation means we don’t “run out of” ability to slice up a big problem into smaller, more-manageable pieces.