Editing Recursion (section)

==In mathematics==
[[File:Sierpinski triangle.svg|thumb|250px|The [[Sierpiński triangle]]—a confined recursion of triangles that form a fractal]]

===Recursively defined sets===
{{Main|Recursive definition}}

====Example: the natural numbers====
{{See also|Closure (mathematics)}}
The canonical example of a recursively defined set is given by the [[natural numbers]]:

:0 is in <math>\mathbb{N}</math>
:if ''n'' is in <math>\mathbb{N}</math>, then ''n'' + 1 is in <math>\mathbb{N}</math>
:The set of natural numbers is the smallest set satisfying the previous two properties.

In mathematical logic, the [[Peano axioms]] (or Peano postulates or Dedekind–Peano axioms), are axioms for the natural numbers presented in the 19th century by the German mathematician [[Richard Dedekind]] and by the Italian mathematician [[Giuseppe Peano]]. The Peano Axioms define the natural numbers referring to a recursive successor function and addition and multiplication as recursive functions.

====Example: Proof procedure ====
Another interesting example is the set of all "provable" propositions in an [[axiomatic system]] that are defined in terms of a [[proof procedure]] which is inductively (or recursively) defined as follows:

*If a proposition is an axiom, it is a provable proposition.
*If a proposition can be derived from true reachable propositions by means of inference rules, it is a provable proposition.
*The set of provable propositions is the smallest set of propositions satisfying these conditions.

===Finite subdivision rules===
{{Main|Finite subdivision rule}}
Finite subdivision rules are a geometric form of recursion, which can be used to create fractal-like images. A subdivision rule starts with a collection of polygons labelled by finitely many labels, and then each polygon is subdivided into smaller labelled polygons in a way that depends only on the labels of the original polygon. This process can be iterated. The standard `middle thirds' technique for creating the [[Cantor set]] is a subdivision rule, as is [[barycentric subdivision]].

===Functional recursion===
A [[function (mathematics)|function]] may be recursively defined in terms of itself. A familiar example is the [[Fibonacci number]] sequence: ''F''(''n'') = ''F''(''n'' − 1) + ''F''(''n'' − 2).  For such a definition to be useful, it must be reducible to non-recursively defined values: in this case ''F''(0) = 0 and ''F''(1) = 1.

===Proofs involving recursive definitions===
Applying the standard technique of [[proof by cases]] to recursively defined sets or functions, as in the preceding sections, yields [[structural induction]] — a powerful generalization of [[mathematical induction]] widely used to derive proofs in [[mathematical logic]] and computer science.

===Recursive optimization===
[[Dynamic programming]] is an approach to [[optimization (mathematics)|optimization]] that restates a multiperiod or multistep optimization problem in recursive form. The key result in dynamic programming is the [[Bellman equation]], which writes the value of the optimization problem at an earlier time (or earlier step) in terms of its value at a later time (or later step).

===The recursion theorem===
In [[set theory]], this is a theorem guaranteeing that recursively defined functions exist. Given a set {{mvar|X}}, an element {{mvar|a}} of {{mvar|X}} and a function {{math|''f'': ''X'' → ''X''}}, the theorem states that there is a unique function <math>F: \N \to X</math> (where <math>\N</math> denotes the set of natural numbers including zero) such that
:<math>F(0) = a</math>
:<math>F(n + 1) = f(F(n))</math>
for any natural number {{mvar|n}}.

Dedekind was the first to pose the problem of unique definition of set-theoretical functions on <math>\mathbb N</math> by recursion, and gave a sketch of an argument in the 1888 essay "Was sind und was sollen die Zahlen?" <ref>A. Kanamori, "[https://math.bu.edu/people/aki/20.pdf In Praise of Replacement]", pp.50--52. Bulletin of Symbolic Logic, vol. 18, no. 1 (2012). Accessed 21 August 2023.</ref>

====Proof of uniqueness====
Take two functions <math>F: \N \to X</math> and <math>G: \N \to X</math> such that:

:<math>F(0) = a</math>
:<math>G(0) = a</math>
:<math>F(n + 1) = f(F(n))</math>
:<math>G(n + 1) = f(G(n))</math>

where {{mvar|a}} is an element of {{mvar|X}}.

It can be proved by [[mathematical induction]] that {{math|1=''F''(''n'') = ''G''(''n'')}} for all natural numbers 
{{mvar|n}}:

:'''Base Case''': {{math|1=''F''(0) = ''a'' = ''G''(0)}} so the equality holds for {{math|1=''n'' = 0}}.

:'''Inductive Step''': Suppose {{math|1=''F''(''k'') = ''G''(''k'')}} for some {{nowrap|<math>k \in \N</math>.}} Then {{math|1=''F''(''k'' + 1) = ''f''(''F''(''k'')) = ''f''(''G''(''k'')) = ''G''(''k'' + 1)}}.
::Hence {{math|1=''F''(''k'') = ''G''(''k'')}} implies {{math|1=''F''(''k'' + 1) = ''G''(''k'' + 1)}}.

By induction, {{math|1=''F''(''n'') = ''G''(''n'')}} for all <math>n \in \N</math>.