Recursive definition

A recursive definition specifies base cases and rules that define new values in terms of previously defined values. It describes objects such as sequences, functions, and recursively generated structures.

Base case: A specified starting value or condition that ends a recursive process. It supplies the initial values from which the definition generates later ones.
Mathematical induction: A proof method establishing a claim for all natural numbers from a base case and an inductive step. Its proof structure mirrors the base-and-step pattern of many recursive definitions.
Fibonacci sequence: The sequence beginning 0, 1 in which each later term is the sum of the two preceding terms. Its familiar terms follow directly from two initial values and one recurrence rule.
Explicit formula: A formula that computes an object's value directly from its input or index. Unlike a recursive rule, it need not refer to earlier values.
Recurrence relation: An equation that defines terms of a sequence using earlier terms. It states the rule that generates later values from the initial terms.
Inductive definition: A definition that specifies basic objects and rules for constructing further objects. It defines sets and structures through formation rules rather than numeric terms.
Factorial: For a nonnegative integer n, the product of all positive integers up to n, with 0! equal to 1. The factorial function is defined by a base value and multiplication by each new input.
Corecursion: A definition of potentially infinite structures by specifying their observable parts from each current state. It defines structures by exposing outputs, rather than reducing each case to smaller inputs.
Well-founded relation: A relation with no infinite descending chains, ensuring recursive descent eventually terminates. A well-founded dependency prevents recursive clauses from descending forever.
Partial function: A function that is defined only for some elements of its intended domain. Recursive rules can fail to yield a value for every input unless termination is established.

Linked from 10 pages