7.1 Recursive Definitions and Structural Induction

Chapter 6 counted objects by describing how a complete outcome is constructed. Many collections, however, do not have a fixed number of construction stages. A binary string may have any finite length, and an arithmetic expression may contain expressions nested inside other expressions.

To describe such collections precisely, we need a rule that can reuse objects already constructed. This is the idea of recursion.

What a recursive definition does

A recursive definition describes new objects in terms of smaller objects of the same kind. A complete recursive definition has three parts:

1. Base rule: names one or more starting objects.

2. Constructor rule: explains how to build a new object from objects already admitted.

3. Closure rule: says that nothing else belongs unless finitely many applications of the first two rules produce it.

The word smaller is essential. Each object must have a finite construction history leading back to a base object. Otherwise the definition could chase itself forever without producing anything.

First example: a recursively generated set of strings

Let $S$ be a set of strings over the symbols $0$ and $1$. We define $S$ by:

• Base: the empty string $\varepsilon$ belongs to $S$.
• Constructor: if $w\in S$, then $w01\in S$.
• Closure: no other strings belong to $S$.

The symbol $\varepsilon$ denotes the string with no symbols, so its length is $0$. The symbol $w$ is a placeholder for any string already known to be in $S$.

Starting from the base, the rules generate

Every constructor step appends one block $01$. Therefore the set can also be described as

where $(01)^n$ means $n$ consecutive copies of the block $01$, and $\mathbb N=\{0,1,2,\ldots\}$.

The string $0101$ belongs because it has a finite certificate:

The string $0110$ does not belong. The only constructor appends $01$, so no legal construction can end in $10$.

Membership is a construction question

For an ordinary set written as a list, membership means finding an item in that list. For a recursively defined set, membership means answering:

> Can the target be built from a base object by finitely many legal constructor steps?

A derivation is the recorded sequence of legal steps. A derivation is useful for two reasons:

• it proves that the object belongs;
• it exposes the smaller objects from which the target was built.

Those smaller objects will later provide the induction hypotheses in a structural proof.

Recursive definitions of numerical functions

Recursion can define numbers as well as sets. The factorial function from Chapter 6 can be defined by

and, for every integer $n\ge1$,

The first equation is the base value. The second equation reduces the input from $n$ to $n-1$. Repeated substitution must eventually reach $0!$.

For example,

This calculation explains why a base value is not optional. Without $0!=1$, the reduction would never produce a numerical answer.

Well-founded reduction prevents circularity

Consider the attempted definition

It mentions $f$ recursively, but it does not reduce the input and gives no base value. Subtracting $f(n)$ from both sides would claim $0=1$, so it cannot define a function.

A useful recursive definition has a size measure that strictly decreases when we follow dependencies backward. Examples are:

• string length;
• the number of operators in an expression;
• an integer input $n$;
• the number of nodes in a finite structure.

Because a nonnegative integer cannot decrease forever, the backward path eventually reaches a base case.

Operate a recursive language workshop. Choose base tiles and constructor rules, grow legal strings from their full derivation histories, and challenge the membership scanner with impostors. The workshop highlights exactly where an illegal object loses its construction certificate.

From construction rules to a proof method

Chapter 3 introduced ordinary mathematical induction. To prove a statement $P(n)$ for every integer $n\ge n_0$, we proved a base case and an induction step from $P(k)$ to $P(k+1)$.

A recursively defined structure may not be arranged in one simple chain. An expression can be built from two smaller expressions, and a tree can have several subtrees. We therefore follow the structure's constructor rules instead of following only the integers.

This method is structural induction.

Suppose a recursive set $R$ has base objects and constructor rules. To prove that every $x\in R$ has property $P(x)$:

1. prove $P(x)$ for every base object; 2. for each constructor, assume $P$ holds for all smaller input objects used by that constructor; 3. use those assumptions to prove $P$ for the newly constructed object.

The assumptions in step 2 are called structural induction hypotheses.

The closure rule then finishes the argument: every object in $R$ has a finite construction, and the proof covers every permitted construction step.

Example: recursively defined expressions

Define a collection $E$ of fully parenthesized expressions:

• Base: the symbol $x$ belongs to $E$.
• Constructor: if $u\in E$ and $v\in E$, then $(u+v)\in E$.
• Closure: nothing else belongs to $E$.

Examples include

For an expression $e\in E$, define:

• $L(e)$ as the number of occurrences of $x$;
• $P(e)$ as the number of plus signs.

We will prove the identity

for every $e\in E$.

Base case

For the base expression $e=x$,

Thus

Constructor step

Suppose the constructor combines smaller expressions $u$ and $v$ to form

Assume the structural induction hypotheses

The new expression contains all leaves from $u$ and $v$, so

It contains the plus signs inside the two subexpressions and one new outer plus sign, so

Substituting the induction hypotheses gives

Therefore the property is preserved by the constructor. The base and constructor cases cover every expression in $E$, so structural induction proves the identity.

Why checking examples is not a proof

We can verify the identity for several expressions:

These checks help us discover the pattern, but the set $E$ is infinite. Structural induction proves the pattern because it verifies every possible way an expression can enter $E$.

Structural recursion and structural induction are partners

The functions $L$ and $P$ were themselves defined by following expression structure:

and

Defining a function by base and constructor clauses is called structural recursion. Proving a property by matching those clauses is structural induction.

The two techniques align:

Grow parenthesized expression trees by merging smaller certified expressions. Each merge updates leaf and operator counts, then asks you to assemble the matching structural-induction step from the two child hypotheses. A live certificate marks any missing base case or constructor case.

Section bridge

Recursive definitions can also generate a sequence of numbers. When the value at index $n$ is related to earlier values, the defining equation is called a recurrence relation. Section 7.2 will learn how to generate, model, and solve such sequences.