4.1 Recursive Definitions and Mathematical Induction: Proving Along the Construction Process

Trees, expressions, directories, and protocol messages can all be constructed from smaller instances of the same kind of object. A recursive definition describes this kind of construction; induction proves properties along the same construction path. The two are closely related but serve different purposes.

What a Complete Recursive Definition Requires

Take the factorial as an example:

0! = 1
n! = n·(n-1)!, n≥1

This includes:

1. Domain: non-negative integers;
2. Base case: a direct definition of the value at the simplest input, 0!;
3. Recursive rule: defining n! in terms of a smaller (n-1)!;
4. Well-foundedness: the parameter decreases with each recursive call, eventually reaching the base case.

A definition like:

f(n) = f(n+1) - 1

lacks a base case and does not guarantee that the recursion moves toward a base case. As a result, it cannot uniquely define a computable function.

For nonnegative integers, f(n)=n+c satisfies the relation for every integer constant c. The missing initial value makes the solution nonunique; it does not make every solution uncomputable.

Recursive Definition of a Sequence

Fibonacci sequence:

F₀ = 0
F₁ = 1
Fₙ = Fₙ₋₁ + Fₙ₋₂, for n ≥ 2

This sequence requires two base cases because the recursive rule depends on the two preceding terms. The mathematical definition does not mandate that a naive recursive program be used to compute it; iterative approaches, matrix exponentiation, and fast doubling are all valid methods for generating the same sequence.

"What the definition says" must be separated from "how the algorithm computes it."

Recursive Data Types

A binary tree can be defined as:

Tree ::= Empty | Node(value, left: Tree, right: Tree)

An arithmetic expression:

Expr ::= Number(n)
       | Add(left: Expr, right: Expr)
       | Multiply(left: Expr, right: Expr)

Recursive definitions specify the minimal closure: objects generated by finitely applying the constructors from base cases belong to the type, and no other objects are included.

Save this complete Java 21 example as TreeDemo.java. The sealed type restricts constructor variants, record patterns unpack nodes, and Empty is an object rather than null; Node rejects null child references. Assume the expanded node count fits int and the runtime can accommodate the depth and allocations. Java 21 finalized the record patterns and switch pattern matching used here.

import java.util.Objects;

public class TreeDemo {
    sealed interface Tree permits Empty, Node { }
    record Empty() implements Tree { }
    record Node(int value, Tree left, Tree right) implements Tree {
        Node {
            Objects.requireNonNull(left);
            Objects.requireNonNull(right);
        }
    }
    static int size(Tree tree) {
        return switch (tree) {
            case Empty ignored -> 0;
            case Node(var value, var left, var right) ->
                1 + size(left) + size(right);
        };
    }
    static Tree mirror(Tree tree) {
        return switch (tree) {
            case Empty ignored -> tree;
            case Node(var value, var left, var right) ->
                new Node(value, mirror(right), mirror(left));
        };
    }
    public static void main(String[] args) {
        Tree e = new Empty();
        Tree t = new Node(1, new Node(2, e, e), new Node(3, e, e));
        System.out.println(size(t));                  // 3
        System.out.println(mirror(mirror(t)).equals(t)); // true
    }
}

Here, recursion descends into strictly nested subtrees. If the data structure allows cycles, it ceases to be a standard finite tree; traversal must include a visited set or some other termination mechanism.

Run javac TreeDemo.java followed by java TreeDemo; the output is 3 and true. Record equality compares components, which suits this small pure-tree example. If two branches share a nonempty subtree, size counts each occurrence; counting distinct objects requires a separate identity-deduplication specification.

Ordinary Mathematical Induction

To prove that a property P(n) holds for all n≥0:

1. Prove the base case P(0);
2. Arbitrarily select k≥0, and assume that P(k) holds;
3. Under that assumption, prove that P(k+1) holds.

Example:

1+2+...+n = n(n+1)/2, n≥1

Base case n=1:

1 = 1·2/2

Inductive step, assuming:

1+...+k = k(k+1)/2

Then:

1+...+k+(k+1)
= k(k+1)/2 + (k+1)
= (k+1)(k+2)/2

This is exactly the formula for n=k+1.

The inductive hypothesis is not "assume the property holds for all numbers," but rather a temporary assumption used only to prove the current step, specifically, that the property holds for the previous value.

Why the Base Case Cannot Be Omitted

Consider the proposition P(n): n≥5. For all k≥0:

If k ≥ 5, then k + 1 ≥ 5

The inductive step holds, but P(0) is false, so we cannot conclude that all non-negative integers are at least 5. The inductive step only propagates truth; it is the base case that initiates the chain.

If a property begins at n₀, then the base case must be P(n₀), and the inductive step must cover all k≥n₀.

Strong Induction

Strong induction allows us to assume, when proving P(k+1), that:

P(n₀), P(n₀+1), ..., P(k)

It is logically equivalent to ordinary induction, but it handles cases where a problem depends on multiple smaller subproblems more naturally.

Theorem: Every integer greater than 1 can be expressed as a product of prime numbers.

The base case n=2 holds because 2 is prime. For n≥3, assume the claim for every 2≤m<n, then split into two cases:

• If n is prime, then it is already a prime product;
• If n is composite, then n=ab for some 1<a,b<n;
• By the strong induction hypothesis, both a and b can be written as products of primes, so n can as well.

The current n depends simultaneously on two smaller, uncertain integers, and strong induction makes those required assumptions directly available.

Structural Induction

For recursively defined data, a proof must cover every constructor.

Theorem: For any finite binary tree t:

mirror(mirror(t)) = t

Proof:

• Empty: Mirroring twice returns the original tree Empty;
• Node(v,l,r): Assume the property holds for the left and right subtrees l and r. The first mirror swaps the left and right subtrees and recursively mirrors each. The second mirror swaps them again and mirrors each subtree. By the induction hypothesis, the subtrees revert to their original forms, so the entire tree is restored.

Structural induction assumes properties based on recursive substructures; there is no need to assign arbitrary indices to nodes. This pattern is widely used in proofs involving compiler abstract syntax trees (ASTs), type expressions, and grammar derivations.

Termination of Recursive Programs

Every recursive call must strictly decrease along some well-founded measure:

int gcd(int a, int b) {
    if (a < 0 || b < 0) throw new IllegalArgumentException("nonnegative inputs required");
    if (b == 0) return a;
    return gcd(b, a % b);
}

This Java method requires a,b≥0, adopts gcd(0,0)=0, and rejects negatives at entry. When b>0, the remainder satisfies 0≤a%b<b, so the second argument strictly decreases. The common divisors are preserved by (a,b)→(b,a%b) until b=0, when the method returns a. The decreasing measure proves termination; divisor preservation proves the result.

For trees, use node count; for lists, use length; for complex states, use lexicographic order of pairs. If recursively traversing a graph, walking along edges does not guarantee structural reduction; additional tracking of visited nodes is required.

This proves termination in the algorithmic model; it does not promise that an arbitrary recursion depth fits a finite call stack. Python’s recursion limit is one visible runtime boundary.

Recursive Definitions and the Boundary of Recursive Execution

• Recursive definitions can be computed iteratively or through other algorithms;
• Iteration itself can be expressed as a recursive state transition;
• Whether either implementation is safe depends on the language's call stack behavior, tail-call optimization, and input scale;
• Java and Python do not guarantee optimizing general tail recursion into constant stack usage, so deep recursion may exhaust the call stack;
• Converting recursion into an explicit stack shifts resource management but does not automatically reduce time complexity.

Completion Checklist

1. Provide recursive definitions for factorial, list length, and expression evaluation.
2. Use ordinary induction to prove that the sum of the first n odd numbers equals n².
3. Use strong induction to prove that any amount greater than or equal to a certain threshold can be formed using combinations of two coin denominations (first verify the proposition and base case).
4. Use structural induction to prove size(mirror(t))=size(t).
5. Specify a clear decreasing termination measure for the Euclidean algorithm or tree traversal.

References

• MIT Mathematics for Computer Science