Editing Recursive definition (section)

==Examples of recursive definitions==

===Elementary functions===
[[Addition]] is defined recursively based on counting as
:<math>\begin{align}
& 0 + a = a, \\
& (1+n) + a = 1 + (n+a).
\end{align}</math>
[[Multiplication]] is defined recursively as
:<math>\begin{align}
& 0 \cdot a = 0, \\
& (1+n) \cdot a = a + n \cdot a.
\end{align}</math>
[[Exponentiation]] is defined recursively as
:<math>\begin{align}
& a^0 = 1, \\
& a^{1+n} = a \cdot a^n.
\end{align}</math>
[[Binomial coefficients]] can be defined recursively as
:<math>\begin{align}
& \binom{a}{0} = 1, \\
& \binom{1+a}{1+n} = \frac{(1+a)\binom{a}{n}}{1+n}.
\end{align}</math>

===Prime numbers===
The set of [[prime number]]s can be defined as the unique set of positive integers satisfying
* [[2 (number)|2]] is a prime number,
* any other positive integer is a prime number if and only if it is not divisible by any prime number smaller than itself.
The primality of the integer 2 is the base case; checking the primality of any larger integer {{mvar|X}} by this definition requires knowing the primality of every integer between 2 and {{mvar|X}}, which is well defined by this definition. That last point can be proved by induction on {{mvar|X}}, for which it is essential that the second clause says "if and only if"; if it had just said "if", the primality of, for instance, the number 4 would not be clear, and the further application of the second clause would be impossible.

===Non-negative even numbers===
The [[even number]]s can be defined as consisting of
* 0 is in the set {{mvar|E}} of non-negative evens (basis clause),
* For any element {{mvar|x}} in the set {{mvar|E}}, {{math|''x'' + 2}} is in {{mvar|E}} (inductive clause),
* Nothing is in {{mvar|E}} unless it is obtained from the basis and inductive clauses (extremal clause).

===Well formed formula===
The notion of a [[well-formed formula]] (wff) in propositional logic is defined recursively as the smallest set satisfying the three rules:

# {{math|p}} is a wff if {{math|p}} is a propositional variable.
#  {{math|¬ p}} is a wff if {{math|p}} is a wff.
# {{math|(p • q)}} is a wff if {{math|p}} and {{math|q}} are wffs  and • is one of the logical connectives  ∨, ∧, →, or ↔.

The  definition can be used to determine whether any particular string of symbols is a wff:

*  {{math|(''p'' ∧ ''q'')}} is a wff, because the propositional variables {{math|''p''}} and {{math|''q''}}  are wffs and {{math|∧}} is a logical connective.

*  {{math|¬ (''p'' ∧ ''q'')}} is a wff, because {{math|(''p'' ∧ ''q'')}} is a wff.

*  {{math|(¬ ''p'' ∧  ¬ ''q'')}} is a wff, because {{math|¬ ''p''}} and {{math|¬ ''q''}} are wffs and {{math|∧}} is a logical connective.