Editing Recursive definition

{{Short description|Defining elements of a set in terms of other elements in the set}}
[[File:KochFlake.svg|thumb|right|Four stages in the construction of a [[Koch snowflake]]. As with many other [[fractal]]s, the stages are obtained via a recursive definition.]]

In [[mathematics]] and [[computer science]], a '''recursive definition''', or '''inductive definition''', is used to define the [[Element (mathematics)|elements]] in a [[Set (mathematics)|set]] in terms of other elements in the set ([[Peter Aczel|Aczel]] 1977:740ff). Some examples of recursively definable objects include [[Factorial|factorials]], [[Natural number|natural numbers]], [[Fibonacci number|Fibonacci numbers]], and the [[Cantor set|Cantor ternary set]].

A [[recursive]] [[definition]] of a [[Function (mathematics)|function]] defines values of the function for some inputs in terms of the values of the same function for other (usually smaller) inputs. For example, the [[factorial]] function {{math|''n''!}} is defined by the rules
:<math>\begin{align}
& 0! = 1. \\
& (n+1)! = (n+1) \cdot n!.
\end{align}</math>

This definition is valid for each natural number {{mvar|n}}, because the recursion eventually reaches the '''[[Base case (recursion)|base case]]''' of&nbsp;0. The definition may also be thought of as giving a procedure for computing the value of the function&nbsp;{{math|''n''!}}, starting from {{math|1=''n'' = 0}} and proceeding onwards with {{math|1=''n'' = 1, 2, 3}} etc.

[[recursion#The recursion theorem|The recursion theorem]] states that such a definition indeed defines a function that is unique. The proof uses [[mathematical induction]].<ref>{{Cite journal|last=Henkin|first=Leon|date=1960|title=On Mathematical Induction|journal=The American Mathematical Monthly|volume=67|issue=4|pages=323–338|doi=10.2307/2308975|issn=0002-9890|jstor=2308975}}</ref>

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 {{tmath|\N}} of [[natural number]]s is:
#0 is in {{tmath|\N.}}
#If an element ''n'' is in {{tmath|\N}} then {{math|''n'' + 1}} is in {{tmath|\N.}}
#{{tmath|\N}} is the smallest set satisfying (1) and (2).

There are many sets that satisfy (1) and (2) – for example, the set {{math|{0, 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&nbsp;0 (or 1), and the property holds of {{math|''n'' + 1}} whenever it holds of {{mvar|n}}, then the property holds of all natural numbers (Aczel 1977:742).

==Form of recursive definitions==
Most recursive definitions have two foundations: a base case (basis) and an inductive clause.

The difference between a [[circular definition]] and a recursive definition is that a recursive definition must always have ''base cases'', cases that satisfy the definition ''without'' being defined in terms of the definition itself, and that all other instances in the inductive clauses must be "smaller" in some sense (i.e., ''closer'' to those base cases that terminate the recursion) — a rule also known as "recur only with a simpler case".<ref>{{Cite web|url=https://www.cis.upenn.edu/~matuszek/cis554-2011/Pages/recursion.html|title=All About Recursion|website=www.cis.upenn.edu|access-date=2019-10-24}}</ref>

In contrast, a circular definition may have no base case, and even may define the value of a function in terms of that value itself — rather than on other values of the function. Such a situation would lead to an [[infinite regress]].

That recursive definitions are valid – meaning that a recursive definition identifies a unique function – is a theorem of set theory known as the [[Recursion#The recursion theorem|recursion theorem]], the proof of which is non-trivial.<ref>For a proof of Recursion Theorem, see [https://www.jstor.org/stable/2308975?seq=1/analyze#page_scan_tab_contents ''On Mathematical Induction'' (1960) by Leon Henkin].</ref> Where the domain of the function is the natural numbers, sufficient conditions for the definition to be valid are that the value of {{math|''f''(0)}} (i.e., base case) is given, and that for {{math|''n'' > 0}}, an algorithm is given for determining {{math|''f''(''n'')}} in terms of {{mvar|n}}, <math>f(0), f(1), \dots, f(n-1)</math> (i.e., inductive clause).

More generally, recursive definitions of functions can be made whenever the domain is a [[Well-order|well-ordered set]], using the principle of [[transfinite recursion]]. The formal criteria for what constitutes a valid recursive definition are more complex for the general case. An outline of the general proof and the criteria can be found in [[James Munkres]]' ''Topology''. However, a specific case (domain is restricted to the positive [[integer]]s instead of any well-ordered set) of the general recursive definition will be given below.<ref name=Munkres>{{cite book|last1=Munkres|first1=James|title=Topology, a first course|date=1975|publisher=Prentice-Hall|location=New Jersey|isbn=0-13-925495-1|page=[https://archive.org/details/topologyfirstcou00munk_0/page/68 68, exercises 10 and 12]|edition=1st|url-access=registration|url=https://archive.org/details/topologyfirstcou00munk_0/page/68}}</ref>

=== Principle of recursive definition ===
Let {{mvar|A}} be a set and let {{math|''a''<sub>0</sub>}} be an element of {{mvar|A}}. If {{mvar|ρ}} is a function which assigns to each function {{mvar|f}} mapping a nonempty section of the positive integers into {{mvar|A}}, an element of {{mvar|A}}, then there exists a unique function <math>h : \Z_+ \to A</math> such that

: <math>\begin{align}
h(1) &= a_0 \\
h(i) &= \rho \left(h|_{\{1,2,\ldots,i-1\}}\right) \text{ for } i>1.
\end{align}</math>

==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.

==Recursive definitions as logic programs==
{{See also|Definition#Logic programs}}
[[Logic programming|Logic programs]] can be understood as sets of recursive  [[definition]]s.<ref>Denecker, M., Ternovska, E.: A logic of nonmonotone inductive definitions. ACM
Trans. Comput. Log. 9(2), 14:1–14:52 (2008)</ref><ref>Warren, D.S. and Denecker, M., 2023. A better logical semantics for prolog. In Prolog: The Next 50 Years (pp. 82-92). Cham: Springer Nature Switzerland.</ref> For example, the recursive definition of even number can be written as the logic program:

<syntaxhighlight lang="prolog">
even(0).
even(s(s(X))) :- even(X).
</syntaxhighlight>

Here <syntaxhighlight lang="prolog" inline>:-</syntaxhighlight> represents ''if'', and <syntaxhighlight lang="prolog" inline>s(X)</syntaxhighlight> represents the successor of <syntaxhighlight lang="prolog" inline>X</syntaxhighlight>, namely <syntaxhighlight lang="prolog" inline>X+1</syntaxhighlight>, as in [[Peano arithmetic]]. 

The logic programming language [[Prolog]] uses [[backward chaining|backward reasoning]] to solve goals and answer queries. For example, given the query <syntaxhighlight lang="prolog" inline>?- even(s(s(0)))</syntaxhighlight> it produces the answer <syntaxhighlight lang="prolog" inline>true</syntaxhighlight>. Given the query <syntaxhighlight lang="prolog" inline>?- even(s(0))</syntaxhighlight> it produces the answer <syntaxhighlight lang="prolog" inline>false</syntaxhighlight>.

The program can be used not only to check whether a query is true, but also to generate answers that are true. For example:

<syntaxhighlight lang="prolog">
?- even(X).
X = 0
X = s(s(0))
X = s(s(s(s(0))))
X = s(s(s(s(s(s(0))))))
.....
</syntaxhighlight>

Logic programs significantly extend recursive definitions by including the use of negative conditions, implemented by [[negation as failure]], as in the definition:

<syntaxhighlight lang="prolog">
even(0).
even(s(X)) :- not(even(X)).
</syntaxhighlight>

== See also ==
*[[Definition]]
*[[Logic programming]]
*[[Mathematical induction]]
*[[Recursive data type]]s
* [[Recursion]]
* [[Recursion (computer science)]]
*[[Structural induction]]

== Notes ==
{{Reflist}}

== References ==

* {{cite book|first=Paul |last=Halmos |author-link=Paul Halmos |title=Naive set theory |url=https://archive.org/details/naivesettheory00halm |url-access=registration |publisher=[[Van Nostrand Reinhold|van Nostrand]] |year=1960 |oclc=802530334}}
* {{cite encyclopedia|first=Peter |last=Aczel |title=An Introduction to Inductive Definitions |year=1977 |encyclopedia=Handbook of Mathematical Logic |editor-first=J. |editor-last=Barwise |isbn=0-444-86388-5 |doi=10.1016/S0049-237X(08)71120-0 |publisher=[[North-Holland Publishing Company|North-Holland]] |author-link=Peter Aczel|series=Studies in Logic and the Foundations of Mathematics |volume=90 |pages=739–782 }}
* {{cite book|first=James L. |last=Hein |year=2010 |title=Discrete Structures, Logic, and Computability |isbn=978-0-7637-7206-2 |publisher=[[Jones & Bartlett Learning|Jones & Bartlett]] |oclc=636352297}}

{{Defining}}

{{DEFAULTSORT:Recursive Definition}}
[[Category:Definition]]
[[Category:Mathematical logic]]
[[Category:Theoretical computer science]]
[[Category:Recursion]]