1
Base clause and recursive clause
The base gives the starting values outright; the recursive clause builds larger objects from smaller ones. Both are required.
Lesson · Induction and Recursion · Recursion
Recursive Definitions
A recursive definition has a base clause and a recursive clause, and together they must reach every object exactly once. Sequences, sets and structures are all defined this way.
BASE 0! = 1
RECURSIVE n! = n · (n−1)! for n ≥ 1
Every object must be reachable from the base in finitely many steps.
Recursive definition ⟷ induction proof: the same structure.
Two clauses, and a reachability condition
Core ideas
What this lesson establishes
A recursive definition is well formed when every object it defines is built from the base in finitely many steps, and nothing is defined twice.
2
The recursion must decrease
Each application must move toward the base. A clause that refers to a larger or equal object defines nothing.
3
Definition and proof mirror each other
A recursive definition with k base clauses is proved about by an induction with k base cases. The shapes match exactly, and that is the point.
The material
Recursive definitions
Sequences, sets and structures, and the condition that makes a definition legitimate.
Recursively defined sequences
factorial 0! = 1 n! = n·(n−1)! n ≥ 1
Fibonacci F₀ = 0, F₁ = 1 Fₙ = Fₙ₋₁ + Fₙ₋₂ n ≥ 2
powers a⁰ = 1 aⁿ = a·aⁿ⁻¹ n ≥ 1
Hanoi H₁ = 1 Hₙ = 2Hₙ₋₁ + 1 n ≥ 2
Fibonacci needs two base values because its recursive clause reaches back two. The number of base clauses is determined by the recursion, not chosen: one fewer and some values would be undefined, one more and the definition might contradict itself.
Definition · Well-formed recursive definition
A recursive definition is well formed when every object in its domain is produced by finitely many applications of the clauses starting from a base object, and the clauses do not assign two different values to one object.
Example · A definition that fails
"f(0) = 1 and f(n) = f(n+1) − 1" defines nothing: computing f(1) requires f(2), which requires f(3), and the recursion never reaches the base. The clause must decrease.
Recursively defined sets
Sets are defined the same way: name some elements outright, then give rules for building more.
Example · The set of even naturals
BASE: 0 ∈ E. RECURSIVE: if n ∈ E then n + 2 ∈ E. Nothing else is in E. That last sentence is not optional — without it the definition permits any superset.
Example · Well-formed parenthesis strings
BASE: the empty string is well formed. RECURSIVE: if s is well formed then so is (s), and if s and t are well formed then so is st. This generates (), (()), ()(), (()()) and nothing else. The Catalan numbers count them, and this path does not reach those.
Recursively defined structures
Example · Binary trees
BASE: the empty tree is a binary tree. RECURSIVE: if L and R are binary trees and v is a value, then the tree with root v, left subtree L and right subtree R is a binary tree. “Rooted Trees and Traversals” in Graphs and Trees traverses exactly this object.
This is where recursion earns its place. A binary tree has no obvious "size parameter" to induct on, but it does have a structure, and “Structural Induction”'s structural induction proves things about it directly.
Theorem · Recursion theorem, informally
Given a base value and a rule producing f(n) from f(n−1), there is exactly one function satisfying both. Existence and uniqueness both follow from induction — which is why recursive definitions are legitimate rather than merely suggestive.
Interactive
Recurrence and closed form
Iterated and solved, then compared
Method
Writing a recursive definition
Base first, then the rule, then the closing sentence.
1
Give enough base cases
As many as the recursive clause reaches back. Fibonacci needs two; a three-term recurrence needs three.
2
Write the recursive clause so it decreases
Every application must move toward a base. A clause referring to a larger argument defines nothing.
3
Say that nothing else qualifies
For a recursively defined set, the sentence "and nothing else is in S" is what makes the definition determinate.
4
Unroll a few values
Computing the first four or five entries catches an off-by-one in the base or the clause immediately.
Recursive definitions
Score 0 / 0Choose the answer you can justify.
The Tower of Hanoi
Moving n discs between three pegs, never placing a larger on a smaller.
To move n discs from A to C:
1. move the top n−1 discs from A to B (Hₙ₋₁ moves)
2. move the largest disc from A to C (1 move)
3. move the n−1 discs from B to C (Hₙ₋₁ moves)
BASE H₁ = 1
RECURSIVE Hₙ = 2Hₙ₋₁ + 1
Unrolling: 1, 3, 7, 15, 31, 63, … = 2ⁿ − 1
With 64 discs and one move per second: 2⁶⁴ − 1 seconds,
about 585 billion years.
The recursive definition came directly from the structure of the problem — the largest disc can only move once everything above it is out of the way — and the closed form came afterwards. “Solving Linear Recurrences” shows how to derive 2ⁿ − 1 rather than guess it.
Common mistakes
1
Too few base casesA two-term recurrence with one base value leaves everything undefined from the second term on. Count the reach of the clause.
2
A recursion that does not decreaseDefining f(n) in terms of f(n+1) or f(n) produces no values at all. Every path must terminate at a base.
3
Omitting the closure sentence for a setThe clauses say what belongs; only the closure says what does not. Without it the definition does not determine a set.
Check your understanding
✓
Finish when you can write a recursive definition and unroll it correctly.
Define the set of binary strings with no two consecutive 1s recursively, and unroll the count for lengths 1 to 6. You should get 2, 3, 5, 8, 13, 21 — Fibonacci, which “Recurrence Relations” explains.
Note: The correspondence between recursive definitions and induction proofs is exact and worth relying on: a definition with two base clauses is proved about by an induction with two base cases, and a clause reaching back k places calls for strong induction.