网站首页  情感咨询  情感美文  情感百科  情感生活  学习充电  旧版美文

请输入您要查询的百科知识：

　

标题 递归函数
类别 哲学
释义 递归函数     recursive function

是使用归纳方法产生的数论函数。 所谓数论函数是定义域和值域皆为自然数的函数。 当用N表示全体自然数(包括0)的集合， 并设A为N的子集时。一个An＝(n≥1)到N中的函数f称为一个n元部分数论函数，或称N上的一个部分函数，或简称为一个部分数论函数。当A=N时，特别把f称为N上的n元全函数，或简称为n元全(数论)函数，这时对任意x1，…，xn∈N，f(x1，…，xn)有定义。全体(部分)递归函数的集合(可用“R”表示)是由三个初始函数出发，经过有限次使用三个构成算子而生成的。构成R的初始函数(或称本原函数)是三类全数论函数：(1)一元零函数Z：对任意x∈N，Z(x)=0。(2)一元后继函数S：对任意x∈N，S(x)=x+1。(3)对任意n≥1，n元投影函数(或称广义么函数)Ini(l≤i≤n)：对任意x1，…，xn∈N，Ini(x1，…，xn)=xi(1≤i≤n)。构成R的算子(即由R中的已有函数生成新函数的运算)有三个：(1)标准迭置(或称复合)。已有m元部分函数f与m个n元部分函数g1，…，gm(m，n≥1)，则如下定义的n元部分函数h称为由f与g1，…，gm使用标准迭置而得：对任意x1，…，xn∈N，h(x1，…，xn)≃f(g1(x1，…，xn)，…，gm(x1，…，xn))，其中“≃”表示在任意〈x1，…，xn〉处左边的函数有定义当且仅当右边的函数有定义，而当左、右两边同时有定义时其值相等。因此函数h在〈x1，…，xn〉处有定义当且仅当函数g1，…，gm都在〈x1，…，xn〉处有定义，并且函数f在〈g1(x1，…，xn)，…，gm(x1，…，xn)〉处有定义。显然当f，g1，…，gm都是全函数时h也为全函数。(2)原始递归式。1.已有一元部分函数g与二元部分函数h，则由下列两个式子确定的一元部分函数f称为由g，h使用原始递归式得到：对任意x∈N，

易见，f在0处有定义当且仅当g在0处有定义;f在y+1处有定义当且仅当对所有z≤y，f在z处有定义，且h在〈z，f(z)〉处有定义。因此当g，h为全函数时，f也为全函数。2.已有n元部分函数g，(n+2)元部分函数h(n≥1)，则由下列两式确定的(n+1)元部分函数f称为由g，h使用原始递归式得到：对任意x1，…，xn，y∈N，

易见，f在〈x1，…，xn，0〉处有定义当且仅当g在〈x1，…，xn〉处有定义，f在〈x1，…，xn，y+1〉处有定义当且仅当对所有z≤y，f在〈x1，…，xn，z〉处有定义，且h在〈x1，…，xn，z，f(x1，…，xn，z)〉处有定义。因此当g，h为全函数时，f也为全函数。(3)μ算子。已有(n+1)元部分函数(n≥1)，则如下定义的n元部分函数f称为由g使用μ算子而得到：对任意x1，…，xn∈N，若存在y，使得对所有z≤y，g(x1，…，xn，z)有定义，且g(x1，…，xn，y)=0，则f(x1，…，xn)等于满足此要求的最小的y;若对所有的y，或者存在z≤y，使得g(x1，…，xn，z)无定义，或者对所有z≤y，g(x1，…，xn，z)有定义，但g(x1，…，xn，y)≠0，则f(x1，…，xn)无定义。这样的f记为：f(x1，…，xn)=μy(g(x1，…，xn，y)=0)。可读为“使得g(x1，…，xn，y)=0且对所有z≤y，g(x1，…，xn，z)有定义的最小的y”。如果g为全函数，且对任意x1，…，xn∈N，有y，使得g(x1，…，xn，y)=0，则称这种g为正则函数，而对正则函数使用μ算子称为μ算子的正常使用，这时所得的函数f也为全函数。R中的一个函数，如果它由初始函数出发只经过有限次使用标准迭置与原始递归式而得，就称为原始递归函数。显然原始递归函数都是全函数。因此原始递归函数也是一般递归函数，但反之不然。可以作出一个函数，它是一般递归的，但不是原始递归的。这样的函数最著名的是阿克曼函数。
随便看

　

依恋情感网情感百科知识大全收录了49620条情感类百科知识词条，覆盖心理学、哲学、美学等领域，基本涵盖了日常生活中常见问题的详细解释，是情感生活的有利工具。

　

Copyright © 2002-2024 yiyi18.com All Rights Reserved
更新时间：2025/8/4 18:36:49