Recursive Definitions in Practice

A recursive definition uses the thing being defined as part of its own definition, and the source says this can be a very powerful technique when it is done right.

Programming

Why Self-Reference Looks Suspicious

Most people meet a rule early in school: a word should not be used to explain itself. A dictionary entry that defines a word using that same word is considered useless, and a teacher would likely mark it wrong. This rule is a good habit for many writing tasks, so it is natural to carry it into any new subject. When you first encounter recursion, you may be tempted to conclude that defining something in terms of itself must be circular, empty, or invalid.

This conclusion is only half right. Defining something partly in terms of itself is not automatically circular. When it is done carefully, it becomes one of the most economical tools for describing complicated things. The rest of this article shows how a recursive definition works, how to recognize one, and why it can say in a few words what would otherwise need an unfinished list.

Checking Whether a Definition Is Recursive

The defining feature of a recursive definition is simple to check. Take a definition, look at the term on the left side, and then look at the words on the right side. If the term being defined shows up again on the right side, the definition is recursive. The check does not depend on how long or short the definition is. It depends only on whether the defined thing refers back to itself.

1
Write down the term being defined (the thing on the left side).
2
Read the words on the right side of the definition.
3
Ask whether the defined term appears again anywhere on the right side.
4
If it does, the definition is recursive. If it does not, the definition is non-recursive, however long it is.

Worked example

Testing the definition of ancestor

Is the following definition recursive? An ancestor is either a parent or an ancestor of a parent.

1
Identify the defined term
The term being defined is 'ancestor'.
2
Scan the right side
The right side contains 'a parent' and 'an ancestor of a parent'.
3
Look for the defined term
The word 'ancestor' appears on the right side inside 'an ancestor of a parent'.
4
Apply the check
Because the defined term appears in its own definition, the definition is recursive. The definition also names 'parent', a plain term that needs no further unpacking here.

Result

The definition is recursive. The self-reference is present, and the plain term 'parent' gives the expansion a way to end.

What do you think happens?

Is this definition recursive? A directory is a part of a disk drive that can hold files and directories.

Yes, because the defined term 'directory' appears on the right side
No, because the definition is short and only mentions files

Reveal answer

Answer:

Yes, because the defined term 'directory' appears on the right side, in the phrase 'directories'.

The check depends only on whether the defined thing refers back to itself, not on length. A directory can hold other directories, so the definition reaches back to 'directory' at a deeper level.

Tracing the Ancestor Definition Step by Step

A recursive definition can be read by repeatedly replacing the defined term with what the definition says about it. Applied to 'ancestor', the first step replaces the word with either a parent or an ancestor of a parent. The second step replaces the second option again, so an ancestor of a parent becomes either a parent of a parent or an ancestor of a parent of a parent. Each replacement moves one generation further back, and the process can continue as far as the situation requires.

When I apply the ancestor definition repeatedly, what does each step produce, and which branches stop while others keep expanding?

The diagram shows the first two replacement steps. The branch that ends in a plain term such as parent stops expanding, while the branch that still contains the word 'ancestor' keeps expanding. This is the practical meaning of a definition that is partly in terms of itself: some branches end in ordinary terms, and the rest lead back to the same definition one level further along.

Why Recursion Compresses Meaning

The real payoff of recursion is compression. Recursive definitions can describe very complex situations with just a few words. To see why, imagine defining 'ancestor' without using recursion. You might write that an ancestor is a parent, or a grandparent, or a great-grandparent, or a great-great-grandparent, and so on. The list is never finished, and the phrase 'and so on' is doing a lot of hidden work. It assumes the reader will continue the pattern correctly, but the definition itself does not say how the pattern continues.

The recursive version handles the same infinite-looking list in one line. It states the pattern once and lets that single statement apply again to whatever it produced. This is why the source describes recursion as a rigorous way of saying 'and so on'. The phrase 'and so on' hints at a repeating pattern, while recursion states the pattern precisely and makes the repetition part of the definition.

Feature	Recursive definition	Definition using 'and so on'
Length	One rule, stated once	A list that is never finished
Pattern	Stated precisely inside the definition	Hinted at, left for the reader to continue
Repetition	Built into the definition by self-reference	Assumed by the reader
Rigor	Rule-based, so every member is pinned down by the same statement	Depends on the reader continuing correctly
Ending	Some branches end in plain terms such as parent	Not specified by the phrase itself

Recursive definition compared with a list closed by 'and so on'

Anatomy of a Recursive Definition

A recursive definition has two kinds of material on its right side. One part refers back to the thing being defined. The other part names an ordinary term that needs no further unpacking. The ordinary term is what keeps the expansion from running forever, because a branch that reaches it stops. In the ancestor definition, 'a parent' is the plain option, and 'an ancestor of a parent' is the self-referencing option.

Which part of the definition refers back to the term being defined, and which part gives an ordinary term where the expansion stops?

Reading the anatomy this way makes the definition easier to trust. The self-reference points the reader back to the same rule one generation further along, and the plain option gives that rule a place to finish for each branch. A definition that only refers back to itself, with no ordinary option, would not describe anything concrete, so good recursive definitions always include both parts.

Following the Directory Example

Recursive definitions are not limited to family trees. Many everyday structures contain smaller copies of themselves. The source offers the directory on a disk drive as an example: a directory is a part of a disk drive that can hold files and directories. Because a directory can hold other directories, the definition reaches back to the word 'directory' at a deeper level.

1
Start with the term directory and its definition: a part of a disk drive that can hold files and directories.
2
Replace the word directory inside the phrase directories with what the definition says about it.
3
The result is a part of a disk drive that can hold files and a part of a disk drive that can hold files and directories.
4
Notice that the directory inside the result can hold files and directories again, so the same replacement applies at one level deeper.
5
The expansion can continue as deep as the folder structure goes, while the file option ends each branch in a plain term.

Mistakes Readers Make With Recursive Definitions

The most common errors come from judging a definition by surface features instead of by the defining check.

Common mistake
Deciding a definition is non-recursive because it is short
What it looks like
A short sentence such as 'a directory is a folder that can hold directories' might seem too simple to be recursive.
Why it fails
The check does not depend on length. It depends only on whether the defined term appears again on the right side.
Do this instead
Look at the left-side term, then search the right side for that same term, however short the definition is.
Common mistake
Treating any self-mention as a definition that is empty
What it looks like
Reading 'an ancestor is a parent or an ancestor of a parent' as the word explaining itself and therefore meaningless.
Why it fails
The definition does not stop at the defined word. It names 'parent', a plain term that gives the expansion a place to end.
Do this instead
Follow the rule one step at a time and check whether some branches end in ordinary terms.
Common mistake
Assuming 'and so on' gives the same precision as a recursive rule
Why it fails
The phrase hints at a repeating pattern but does not say how the pattern continues.
Do this instead
Restate the pattern as a single recursive rule that applies to whatever it produced.
Common mistake
Expanding a recursive definition without checking for an ordinary option
Why it fails
A definition whose only option refers back to itself does not describe anything concrete.
Do this instead
Confirm that the definition has at least one branch that ends in a plain term before trusting it.

Practice Testing Recursive Definitions

MEDIUM

For each definition below, decide whether it is recursive by checking whether the defined term appears on its own right side. Then trace one expansion step: (a) A sentence is a word followed by a sentence, or a word. (b) A pet is an animal kept at home. (c) A set of files is a folder that can hold files or other sets of files.

Hints

Start by writing down the left-side term for each definition.
Search the right side for that same word, ignoring whether the definition is long or short.
For the recursive ones, identify which branch ends in a plain term and which branch refers back.

Your attempt (not saved)