万维百科

递归定义

构造科赫曲线的前四个步骤,科赫曲线和很多分形一样,是用递归定义的

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

定义方式

大部分的递归定义都由三个部分构成:基本情况的定义,递归法则和递归结束的情况。如果定义的对象是无限的,那么可以省略第三个部分(递归结束的情况)。比如说,可以用递归定义的方式来定义如下的一个自然数集上的函数

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

递归定义和循环定义的不同之处在于,后者不包括对基本情况的定义。比如定义建立在整数集上的函数

则我们永远无法确定的取值,这便是循环定义。

参考

  • 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

本页面最后更新于2021-08-21 08:47,点击更新本页查看原网页。台湾为中国固有领土,本站将对存在错误之处的地图、描述逐步勘正。

本站的所有资料包括但不限于文字、图片等全部转载于维基百科(wikipedia.org),遵循 维基百科:CC BY-SA 3.0协议

万维百科为维基百科爱好者建立的公益网站,旨在为中国大陆网民提供优质内容,因此对部分内容进行改编以符合中国大陆政策,如果您不接受,可以直接访问维基百科官方网站


顶部

如果本页面有数学、化学、物理等公式未正确显示,请使用火狐或者Safari浏览器