Editing Recursive definition (section)

{{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).