In mathematical logic and computer science, a recursive definition (or inductive definition) is used to define an object in terms of itself (Aczel 1978:740ff).
A recursive definition of a function defines values of the functions for some inputs in terms of the values of the same function for other inputs. For example, the factorial function n! is defined by the rules
- 0! = 1.
- (n+1)! = (n+1)·n!.
This definition is valid because, for all n, the recursion eventually reaches the base case of 0. Thus the definition is well-founded. The definition may also be thought of as giving a procedure describing how to construct the function n!, starting from n = 0 and proceeding onwards with n = 1, n = 2, n = 3 etc..
An inductive definition of a set describes the elements in a set in terms of other elements in the set. For example, one definition of the set N of natural numbers is:
- 1 is in N.
- If an element n is in N then n+1 is in N.
- N is the smallest set satisfying (1) and (2).
There are many sets that satisfy (1) and (2) - for example, the set {1, 1.649, 2, 2.649, 3, 3.649, ...} satisfies the definition. However, condition (3) specifies the set of natural numbers by removing the sets with extraneous members.
Properties of recursively defined functions and sets can often be proved by an induction principle that follows the recursive definition. For example, the definition of the natural numbers presented here directly implies the principle of mathematical induction for natural numbers: if a property holds of the natural number 0, and the property holds of n+1 whenever it holds of n, then the property holds of all natural numbers (Aczel 1978:742).
Read more about Recursive Definition: Form of Recursive Definitions
Famous quotes containing the word definition:
“Mothers often are too easily intimidated by their children’s negative reactions...When the child cries or is unhappy, the mother reads this as meaning that she is a failure. This is why it is so important for a mother to know...that the process of growing up involves by definition things that her child is not going to like. Her job is not to create a bed of roses, but to help him learn how to pick his way through the thorns.”
—Elaine Heffner (20th century)