1) recursive function
递归函数
1.
Analysis of recursive function s time complexity;
递归函数时间复杂度的分析
2.
Traditional Gene Expression Programming(GEP) is bare of discovering recursive functions.
传统基因表达式编程(GEP)无法发现递归函数。
3.
Recursive functions on context-free languages (CFRF) are a kind of new recursive functions proposed especially for describing non-numerical algorithms used on computers.
上下文无关语言上递归函数(recursive functions on context-free languages,简称 CFRF)是为描述计算机上用的非数值算法而提出的一种新型递归函数。
2) recursive functions
递归函数
3) recursion function
递归函数
5) recursive functions class
递归函数类
6) recursive set functions
递归集函数
1.
In this paper, the notions of recursive functions and recursive formulas on sets are introduced; some properties of such functions and formulas are studied; and the relations between recursive set functions and primitively recursive set functions are defined by Jenson and Karp and between recursive set functions and recursive number theoretic functions are also discussed.
研究了递归集函数的初步性质，讨论了递归集函数与Ｊｅｎｓｅｎ和Ｋａｒｐ定义的原始递归集函数及递归数论函数之间的关系，并给出了ＺＦＣ的可定义集模型上递归集函数的范式定理。
补充资料：递归函数
数论函数的一种,其定义域与值域都是自然数集,只是由于构作函数方法的不同而有别于其他的函数。处处有定义的函数叫做全函数，未必处处有定义的函数叫做部分函数。最简单又最基本的函数有三个:零函数O(x)=0(其值恒为0);射影函数；后继函数S(x)=x+1。它们合称初始函数。要想由旧函数作出新函数，必须使用各种算子。
代入（又名复合或叠置）是最简单又最重要的造新函数的算子，其一般形状是：由一个m元函数??与m个n元函数 g1,g2,...,gm 造成新函数 ?? (g1(x1,x2,...,xn)，g2(x1,x2,...,xn),...,gm(x1,x2，...，xn)),亦可记为??(g1，g2,...,gm)(x1，x2,...,xn)。另一个造新函数的算子是原始递归式。具有n个参数u1，u2,...,un的原始递归式为：具有一个参数的原始递归式可简写为：其特点是，不能由g、h两函数直接计算新函数的一般值??(u,x),而只能依次计算??(u,0)，??(u,1)，??(u,2)，...；但只要依次计算，必能把任何一个??(u,x)值都算出来。换句话说只要g,h为全函数且可计算，则新函数f也是全函数且可计算。
由初始函数出发，经过有限次的代入与原始递归式而作出的函数叫做原始递归函数。由于初始函数显然是全函数且可计算，故原始递归函数都是全函数且可计算。通常使用的数论函数全是原始递归函数，可见原始递归函数是包括很广的。但是W.阿克曼证明了，可以作出一个可计算的全函数，它不是原始递归的。经过后人改进后，这个函数可写为如下定义的阿克曼函数：容易看出,这个函数是处处可计算的。任给m,n的值，如果m为0，可由第一式算出；如果m不为0而n为0，可由第二式化归为求g(m,1)的值，这时第一变目减少了；如果m，n均不为0,根据第三式可先计算g(m,n-1),设为α，再计算g(m-1,α),前者第二变目减少（第一变目不变）,后者第一变目减少。极易用归纳法证得，这样一步一步地化归,最后必然化归到第一变目为0，从而可用第一式计算。所以这个函数是处处可计算的。此外又容易证明，对任何一个一元原始递归函数??(x),永远可找出一数α使得??(x)(α,x)。这样，g(x,x)+1便不是原始递归函数，否则将可找出一数b使得g(x,x)+1(b,x)。令x=b，即得g(b,b)+1(b,b)，而这是不可能的。
另一个重要的造新函数的算子是造逆函数的算子，例如，由加法而造减法，由乘法造除法等。一般，设已有函数??(u,x),就x解方程??(u,x)=t,可得x=g(u,t)。这时函数g叫做??的逆函数。至于解一般方程??(u，t,x)=0而得x＝g(u，t)可以看作求逆函数的推广。解方程可以看作使用求根算子。??(u,t，x)=0的最小x根（如果有根的话），记为μx[??(u,t,x)=0]。当方程没有根时,则认为μx[??(u,t,x)=0]没有定义。可见,即使??(u,t,x)处处有定义且可计算,但使用求根算子后所得的函数μx[??(u,t,x)=0]仍不是全函数,可为部分函数。但只要它有定义，那就必然可以计算。这算子称为μ算子。如果??(u,t,x)本身便是部分函数，则 μx[??(u,t,x)=0]的意义是：当??(u,t,n)可计算且其值为0,而x时??(u,t,x)均可计算而其值非0，则 μx[??(u,t,x)=0]指n；其他情况则作为无定义。例如，如果??(u,t,x)=0根本没有根，或者虽然知道有一根为n，但??(u,t,n-1)不可计算,那么 μx[??(u,t,x)=0]都作为没有定义。在这样定义后,只要 μx[??(u,t,x)=0]有值便必可计算。由初始函数出发,经过有穷次使用代入、原始递归式与 μ算子而作成的函数叫做部分递归函数，处处有定义的部分递归函数称为全递归函数，或一般递归函数。
原始递归函数类里还有一个重要的子类称为初等函数类,它是由非负整数与变元经过有穷次加、算术减（即｜α-b｜）、乘、算术除、叠加Σ、叠乘П而得的函数组成的类。
波兰人A.格热高契克把原始递归函数类按定义的复杂程度来分类，称为格热高契克分层或波兰分层。
要把递归函数应用于谓词，首先要定义谓词的特征函数。谓词R(x,y)的特征函数是称谓词R 是递归谓词，若R 的特征函数是递归函数；称自然数子集A为递归集,若谓词x∈A是递归谓词。有了上述定义，就可以用递归函数来处理递归谓词和递归集。为了处理N×N（其中N 为自然数集）的子集，就要建立配对函数,所谓配对函数通常是指由N×N 到N 的一个函数??(x，y)与它的逆函数g1(z)，g2(z)。它们都满足以下关系：
可以构造许多原始递归的配对函数。
递归函数也可以用来处理符号串。处理的办法是对符号及符号串配以自然数。这方法是K.哥德尔开始引进的，因此称为哥德尔配数法。例如，在要处理的符号系统｛α1，α2，α3,...｝中，可以用奇数1，3，5，7，...作为α1,α2，α3，α4，...的配数，符号串以为其配数,其中Ps是第s个素数,nij是αij的配数。这种配数称为哥德尔配数。有了哥德尔配数法，就可以用递归函数来描写、处理有关符号串的谓词了。
代入（又名复合或叠置）是最简单又最重要的造新函数的算子，其一般形状是：由一个m元函数??与m个n元函数 g1,g2,...,gm 造成新函数 ?? (g1(x1,x2,...,xn)，g2(x1,x2,...,xn),...,gm(x1,x2，...，xn)),亦可记为??(g1，g2,...,gm)(x1，x2,...,xn)。另一个造新函数的算子是原始递归式。具有n个参数u1，u2,...,un的原始递归式为：具有一个参数的原始递归式可简写为：其特点是，不能由g、h两函数直接计算新函数的一般值??(u,x),而只能依次计算??(u,0)，??(u,1)，??(u,2)，...；但只要依次计算，必能把任何一个??(u,x)值都算出来。换句话说只要g,h为全函数且可计算，则新函数f也是全函数且可计算。
由初始函数出发，经过有限次的代入与原始递归式而作出的函数叫做原始递归函数。由于初始函数显然是全函数且可计算，故原始递归函数都是全函数且可计算。通常使用的数论函数全是原始递归函数，可见原始递归函数是包括很广的。但是W.阿克曼证明了，可以作出一个可计算的全函数，它不是原始递归的。经过后人改进后，这个函数可写为如下定义的阿克曼函数：容易看出,这个函数是处处可计算的。任给m,n的值，如果m为0，可由第一式算出；如果m不为0而n为0，可由第二式化归为求g(m,1)的值，这时第一变目减少了；如果m，n均不为0,根据第三式可先计算g(m,n-1),设为α，再计算g(m-1,α),前者第二变目减少（第一变目不变）,后者第一变目减少。极易用归纳法证得，这样一步一步地化归,最后必然化归到第一变目为0，从而可用第一式计算。所以这个函数是处处可计算的。此外又容易证明，对任何一个一元原始递归函数??(x),永远可找出一数α使得??(x)
另一个重要的造新函数的算子是造逆函数的算子，例如，由加法而造减法，由乘法造除法等。一般，设已有函数??(u,x),就x解方程??(u,x)=t,可得x=g(u,t)。这时函数g叫做??的逆函数。至于解一般方程??(u，t,x)=0而得x＝g(u，t)可以看作求逆函数的推广。解方程可以看作使用求根算子。??(u,t，x)=0的最小x根（如果有根的话），记为μx[??(u,t,x)=0]。当方程没有根时,则认为μx[??(u,t,x)=0]没有定义。可见,即使??(u,t,x)处处有定义且可计算,但使用求根算子后所得的函数μx[??(u,t,x)=0]仍不是全函数,可为部分函数。但只要它有定义，那就必然可以计算。这算子称为μ算子。如果??(u,t,x)本身便是部分函数，则 μx[??(u,t,x)=0]的意义是：当??(u,t,n)可计算且其值为0,而x
原始递归函数类里还有一个重要的子类称为初等函数类,它是由非负整数与变元经过有穷次加、算术减（即｜α-b｜）、乘、算术除、叠加Σ、叠乘П而得的函数组成的类。
波兰人A.格热高契克把原始递归函数类按定义的复杂程度来分类，称为格热高契克分层或波兰分层。
要把递归函数应用于谓词，首先要定义谓词的特征函数。谓词R(x,y)的特征函数是称谓词R 是递归谓词，若R 的特征函数是递归函数；称自然数子集A为递归集,若谓词x∈A是递归谓词。有了上述定义，就可以用递归函数来处理递归谓词和递归集。为了处理N×N（其中N 为自然数集）的子集，就要建立配对函数,所谓配对函数通常是指由N×N 到N 的一个函数??(x，y)与它的逆函数g1(z)，g2(z)。它们都满足以下关系：
可以构造许多原始递归的配对函数。
递归函数也可以用来处理符号串。处理的办法是对符号及符号串配以自然数。这方法是K.哥德尔开始引进的，因此称为哥德尔配数法。例如，在要处理的符号系统｛α1，α2，α3,...｝中，可以用奇数1，3，5，7，...作为α1,α2，α3，α4，...的配数，符号串以为其配数,其中Ps是第s个素数,nij是αij的配数。这种配数称为哥德尔配数。有了哥德尔配数法，就可以用递归函数来描写、处理有关符号串的谓词了。
说明：补充资料仅用于学习参考，请勿用于其它任何用途。
参考词条