查看“︁递归定义”︁的源代码

[[File:KochFlake.svg|thumb|right|构造科赫曲线的前四个步骤，科赫曲线和很多分形一样，是用递归定义的]]
'''递归定义'''是[[数理逻辑]]和[[计算机科学]]用到的一种[[定义]]方式，使用被定义对象的自身来为其下定义（简单说就是自我复制的定义）。递归定义与归纳定义类似，但也有不同之处。递归定义中使用被定义对象自身来定义，而归纳定义是使用被定义对象的已经定义的部分来定义尚未定义的部分。不过，使用递归定义的函数或集合，它们的性质可以用[[数学归纳法]]，通过递归定义的内容来证明。

== 定义方式 ==
大部分的递归定义都由三个部分构成：基本情况的定义，递归法则和递归结束的情况。如果定义的对象是无限的，那么可以省略第三个部分（递归结束的情况）。比如说，可以用[[递归]]定义的方式来定义如下的一个[[自然数]]集上的[[函数]]<math>f</math>：
:<math>f(0) = 1</math>
:<math>\forall n > 0, \, \, f(n) = n \times f(n-1).</math>
这个定义在[[逻辑]]上是成立的，因为它首先定义了<math>f</math>在最小的自然数0上的取值，接下来对每个大于零的自然数<math>n</math>，只要重复有限多次定义的过程，最终就会回到对0的定义上。这样定义出的函数<math>f</math>就是[[阶乘]]函数。

递归定义和[[循环定义]]的不同之处在于，后者不包括对基本情况的定义。比如定义建立在[[整数]]集上的函数<math>g</math>：
:<math>\forall n \in \mathbb{Z}, \, \, g(n) = g(n-1) + 1,</math></center>

则我们永远无法确定<math>g</math>的取值，这便是循环定义。

==递归定义的原理==
基于[[递归定理]]，设<math>A</math>是一个集合，并且设<math>a_0</math>是<math>A</math>的一个元素；如果有函数<math>\rho : f_i \mapsto a_k</math>，为每个映射[[正数|正]][[整数|整数集]]的非空子集至<math>A</math>的函数<math>f_i</math>，指派<math>A</math>的一个元素<math>a_k</math>，那么存在一个唯一的函数<math>h : \Z_+ \to A</math>使得：

: <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>
这里的<math>f\vert_A</math>表示将<math>f</math>[[限制 (数学)|限制]]于<math>A</math>。

== 参考 ==
* P. Aczel (1977), "An introduction to inductive definitions", ''Handbook of Mathematical Logic'', J.&nbsp;Barwise&nbsp;(ed.), ISBN 0-444-86388-5
* James L. Hein (2009), ''Discrete Structures, Logic, and Computability''. ISBN 0-7637-7206-2
[[Category:递归论]]
[[Category:定义]]
[[Category:理论计算机科学]]
[[Category:數理邏輯]]
[[Category:递归]]