递归定义

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

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

• 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