Editing Recursive definition (section)

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