递归定义

递归定义是数理逻辑和计算机科学用到的一种定义方式，使用被定义对象的自身来为其下定义（简单说就是自我复制的定义）。递归定义与归纳定义类似，但也有不同之处。递归定义中使用被定义对象自身来定义，而归纳定义是使用被定义对象的已经定义的部分来定义尚未定义的部分。不过，使用递归定义的函数或集合，它们的性质可以用数学归纳法，通过递归定义的内容来证明。

大部分的递归定义都由三个部分构成：基本情况的定义，递归法则和递归结束的情况。如果定义的对象是无限的，那么可以省略第三个部分（递归结束的情况）。比如说，可以用递归定义的方式来定义如下的一个自然数集上的函数${\displaystyle f}$：

${\displaystyle f(0)=1}$

${\displaystyle \forall n>0,\,\,f(n)=n\times f(n-1).}$

这个定义在逻辑上是成立的，因为它首先定义了${\displaystyle f}$在最小的自然数0上的取值，接下来对每个大于零的自然数${\displaystyle n}$，只要重复有限多次定义的过程，最终就会回到对0的定义上。这样定义出的函数${\displaystyle f}$就是阶乘函数。

递归定义和循环定义的不同之处在于，后者不包括对基本情况的定义。比如定义建立在整数集上的函数${\displaystyle g}$：

${\displaystyle \forall n\in \mathbb {Z} ,\,\,g(n)=g(n-1)+1,}$

则我们永远无法确定${\displaystyle g}$的取值，这便是循环定义。

基于递归定理，设${\displaystyle A}$是一个集合，并且设${\displaystyle a_{0}}$是${\displaystyle A}$的一个元素；如果有函数${\displaystyle \rho :f_{i}\mapsto a_{k}}$，为每个映射正整数集的非空子集至${\displaystyle A}$的函数${\displaystyle f_{i}}$，指派${\displaystyle A}$的一个元素${\displaystyle a_{k}}$，那么存在一个唯一的函数${\displaystyle h:\mathbb {Z} _{+}\to A}$使得：

${\displaystyle {\begin{aligned}h(1)&=a_{0}\\h(i)&=\rho \left(h|_{\{1,2,\ldots ,i-1\}}\right){\text{ for }}i>1\end{aligned}}}$

这里的${\displaystyle f\vert _{A}}$表示将${\displaystyle f}$限制于${\displaystyle A}$。

• P. Aczel (1977), "An introduction to inductive definitions", Handbook of Mathematical Logic, J. Barwise (ed.), ISBN 0-444-86388-5
• James L. Hein (2009), Discrete Structures, Logic, and Computability. ISBN 0-7637-7206-2