Writing Clear Definitions
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.
Try it: The Call Stack
How the call stack keeps track of function calls: each call pushes a frame with its own arguments and local variables, and each return pops it.
How it works
- Calling a function pushes a new frame on top of the stack; the caller pauses.
- The frame holds that call's parameters and local variables.
- When the function returns, its frame is popped and the return value goes back to the paused caller.
- A recursive function pushes one frame per call until the base case, then the frames unwind in reverse order.
Default run (17 steps): Program starts: main is about to call factorial(4). … The stack is empty again. Result: 24. Deepest point: 4 frames, 4 calls in total.
Loading the simulation…
Why Self-Reference Looks Suspicious
Most people learn early in school that 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 is a sound habit for many kinds of writing, so it is natural to carry it into a new subject. When you first meet recursion, you may conclude that defining something in terms of itself must be circular, empty, or invalid.
The source argues that 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 to recognize such a definition, how it unfolds, and why it can say more with less than a list of cases ever could.
What do you think happens?
Before reading on: is the definition 'an ancestor is either a parent or an ancestor of a parent' recursive?
Reveal answer
Yes, it is recursive. The defined term 'ancestor' appears again on the right side of the definition.
A definition is recursive whenever the term being defined shows up in its own definition. Being recursive does not make a definition invalid. The next section explains how to check this for yourself.
Applying the Self-Reference Test
The defining feature of a recursive definition is simple to check. Look at the term on the left side of the definition, which is the thing being defined. Then look at the words on the right side. If the defined term shows up again on the right, the definition is recursive. The test does not depend on how long or short the definition is. It depends only on whether the defined thing refers back to itself.
In the ancestor definition, the word 'ancestor' is being defined and also appears on the right side, so the definition is recursive. The definition also names 'parent', which is a plain term that needs no further unpacking in this definition. The definition therefore has two kinds of words: the defined term that returns, and ordinary terms that do not.
Checking Three Definitions for Self-Reference
Decide whether each of these definitions is recursive by checking whether the defined term appears on the right side. The first two are original examples written for this article.
- 1Definition A
A list is either empty or an item followed by a list. The defined term 'list' appears again on the right side after 'followed by a'. The definition is recursive.
- 2Definition B
A triangle is a shape with three straight sides. The defined term 'triangle' does not appear on the right side. The definition is not recursive, even though it is short and complete.
- 3Definition C
A directory is a part of a disk drive that can hold files and directories. The defined term 'directory' appears again on the right side, so the definition is recursive. Length did not decide the answer.
Definitions A and C are recursive because the defined term appears on the right side. Definition B is not recursive. The check depends only on whether the defined term refers back to itself.
Unfolding a Recursive Definition
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.
Read the diagram from top to bottom. Each row applies the same rule to the one remaining instance of the defined term. Plain terms such as parent end their part of the expansion, while the term ancestor keeps producing new rows. The process stops when a branch reaches only plain terms, which is the practical ending of the expansion.
Why Recursion Beats 'And So On'
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 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 never says how the pattern continues.
| Feature | Phrase with 'and so on' | Recursive definition |
|---|---|---|
| Length | Grows with each extra case listed | Stated once, in one line |
| Pattern | Hinted at, left for the reader to continue | Stated precisely as part of the definition |
| Coverage | Only the cases written out, plus a hope the rest follow | Applies again to whatever it produces, so the repetition is built in |
| Next step | Not defined by the text | Defined by the same rule applied one level further along |
Describing an unbounded pattern in two ways, as summarized from the source
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 hints at a repeating pattern, while recursion states the pattern precisely and makes the repetition part of the definition.
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 one example. Because a directory can hold other directories, the definition reaches back to the word 'directory' at a deeper level. The source also lists sentence, set, and Java statement as further examples of terms defined partly in terms of themselves.
The tree shows the practical meaning of a definition that is partly in terms of itself. Some branches end in ordinary terms such as parent. The rest lead back to the same definition one level further along. A single compact rule therefore covers a structure that would otherwise need an unbounded list.
Practice Spotting Recursive Definitions
For each definition below, state whether it is recursive and name the term that causes your answer. Definition 1: A staircase is a single step followed by a staircase, or a single step alone. Definition 2: A step is the flat part of a stair where a foot rests. Definition 3: A path is a single square, or a square followed by a path. Explain your answer by pointing to where the defined term appears on the right side.
Hints
- Start by writing down the term on the left side of each definition.
- Scan the right side for that exact term. Ignore how long the definition is.
- Definition 2 uses the word 'step' on the right side. Check whether that is the same defined term.
Mistakes Beginners Make
Common mistake Concluding that any definition using its own term is circular and therefore invalid
What it looks likeAn ancestor is either a parent or an ancestor of a parent.
Why it failsThe source says defining something partly in terms of itself is not automatically circular. The self-reference is what lets the definition reach across many generations.
Do this insteadRecognize the self-reference, then ask whether the definition reaches plain terms that end each branch. A recursive definition can be valid and useful.
Common mistake Deciding recursion depends on how long the definition is
What it looks likeA short definition is judged non-recursive, while a long one is judged recursive.
Why it failsThe defining feature is only whether the defined term appears on the right side, regardless of length.
Do this insteadLocate the defined term on the left, then search the right side for it. Length is irrelevant to the test.
Common mistake Treating 'and so on' as a complete definition
What it looks likeAn ancestor is a parent, or a grandparent, or a great-grandparent, and so on.
Why it failsThe phrase assumes the reader will continue the pattern correctly, and the text never says how it continues.
Do this insteadState the repeating pattern once in a recursive rule, so the repetition is part of the definition itself.
Common mistake Forgetting that plain terms such as parent end a branch, so expansion stops there rather than continuing forever
Key Takeaways
- A recursive definition uses the term being defined as part of its own definition, and the source says this can be a very powerful technique when done right.
- To test for recursion, look at the defined term on the left and check whether it appears again on the right, regardless of the definition's length.
- Unfolding a recursive definition means repeatedly replacing the defined term with what the definition says about it, while plain terms end their branches.
- Recursive definitions describe complex situations in few words and are more rigorous than phrases like 'and so on', which leave the next step undefined.