|
递归函数 递归函数 阿克曼提出的数学概念  递归函数是数论函数的一种，其定义域与值域都是自然数集，只是由于构作函数方法的不同而有别于其他的函数。最简单又最基本的函数有三个：零函数O(x)=0(其值恒为0)，射影函数，后继函数S(x)=x+1，它们合称初始函数。要想由旧函数作出新函数，必须使用各种算子。 在数理逻辑和计算机科学中，递归函数或μ-递归函数是一类从自然数到自然数的函数，它是在某种直觉意义上是'可计算的'。事实上，在可计算性理论中证明了递归函数精确的是图灵机的可计算函数。 基本信息
定理定义 数论函数的一种，其定义域与值域都是自然数集,只是由于构作函数方法的不同而有别于其他的函数。处处有定义的函数叫做全函数，未必处处有定义的函数叫做部分函数。最简单又最基本的函数有三个：零函数O(x)=0(其值恒为0);射影函数  代入（又名复合或叠置）是最简单又最重要的造新函数的算子，其一般形状是：由一个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.阿克曼证明了，可以作出一个可计算的全函数，它不是原始递归的。经过后人改进后，这个函数可写为如下定义的阿克曼函数：  递归函数 另一个重要的造新函数的算子是造逆函数的算子，例如，由加法而造减法，由乘法造除法等。一般，设已有函数ƒ(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<n时ƒ(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)的特征函数是   递归函数也可以用来处理符号串。处理的办法是对符号及符号串配以自然数。这方法是K.哥德尔开始引进的，因此称为哥德尔配数法。例如，在要处理的符号系统｛α1，α2，α3,…｝中，可以用奇数1，3，5，7，…作为α1,α2，α3，α4，…的配数，符号串   运用 C++语言 (一) 目的：将1号和2号从A移到B 调用函数：hanoi(2,'A', 'C', 'B')。 在hanoi(2,'A', 'C', 'B')中递归调用如下： A-->C----hanoi(1,'A', 'B', 'C') A-->B----hanoi(1,'A', 'C', 'B') C-->B----hanoi(1,'C', 'A', 'B') (二) 目的：将3号从A移到C 调用函数：hanoi(1,'A', 'B', 'C') A-->C (三) 目的：将1号和2号从B移到C 调用函数：hanoi(2,'B', 'A', 'C') 在hanoi(2,'B', 'A', 'C')中递归递归如下： B-->A----hanoi(1,'B', 'C', 'A') B-->C----hanoi(1,'B', 'A', 'C') A-->C----hanoi(1,'A', 'B', 'C') 总共调用了7次函数， 只要hanoi()的第一个参数大于1，它就会在内部调用自身3次，“直到第一个参数＝1，然后调用printf()”。 hanoi(n, ...)调用hanoi(1, ...)的次数为2的n次方减去一。 pascal语言 【pascal语言】 function do(x:integer); begin if x<=1 then exit(0) else if x>1then exit(do(x-1)+10) end; 【C++语言】 用递归法计算1+2+。。。N的值。 #include<iostream.h> int fn(int i); void main() { int N; cout<<'\n输入一个正整数:'; cin>>N; cout<<'\n 1+2+...+'<<N<<'的结果是:'<<fn(N)<<'\n'; } //递归函数的定义 int fn(int i) { if(i==1) return 1; else return i+fn(i-1); } 正确写出 如何快速正确的写出递归函数？写一个递归函数是非常程式化的东西，只要按照一定的规则来写，就可以很容易地写出递归函数。写递归函数有三步： ①写出迭代公式； ②确定递归终止条件； ③将①②翻译成代码。以求n！为例： ①写出迭代公式：n！的迭代公式为 ②确定递归终止条件：1！＝1就是递归终止条件 ③将①②翻译成代码：将迭代公式等号右边的式子写入return语句中，即return （fact（n-1））*n;long fact（int n） { if （n==1） return 1; return （fact（n-1））*n; } 下面再举一个例子，希望能帮助大家进一步体会这一原则 写一个函数，求：f（n）=1+2+3+……+n的值 ①写出迭代公式：迭代公式为 ②确定递归终止条件：f（1）＝1就是递归终止条件 ③将①②翻译成代码：将迭代公式等号右边的式子写入return语句中，即return （Sum（n-1））+n; 将1！＝1翻译成判断语句：if（n==1） return 1; 按照先测试，后递归的原则写出代码。 long Sum（int n） { if （n==1） return 1; return （Sum（n-1））+n; } Oracle用法 Oraclestart with connect by 用法 oracle中 connect by prior 递归算法 Oracle中start with...connect by prior子句用法 connect by 是结构化查询中用到的，其基本语法是： select ... from tablename start with 条件1 connect by 条件2 where 条件3; 例： select * from table start with org_id = 'HBHqfWGWPy' connect by prior org_id = parent_id; 简单说来是将一个树状结构存储在一张表里，比如一个表中存在两个字段: org_id,parent_id那么通过表示每一条记录的parent是谁，就可以形成一个树状结构。 用上述语法的查询可以取得这棵树的所有记录。 其中： 条件1 是根结点的限定语句，当然可以放宽限定条件，以取得多个根结点，实际就是多棵树。 条件2 是连接条件，其中用PRIOR表示上一条记录，比如 CONNECT BY PRIOR org_id = parent_id就是说上一条记录的org_id 是本条记录的parent_id，即本记录的父亲是上一条记录。 条件3 是过滤条件，用于对返回的所有记录进行过滤。 简单介绍如下： 早扫描树结构表时，需要依此访问树结构的每个节点，一个节点只能访问一次，其访问的步骤如下： 第一步：从根节点开始； 第二步：访问该节点； 第三步：判断该节点有无未被访问的子节点，若有，则转向它最左侧的未被访问的子节，并执行第二步，否则执行第四步； 第四步：若该节点为根节点，则访问完毕，否则执行第五步； 第五步：返回到该节点的父节点，并执行第三步骤。 总之：扫描整个树结构的过程也即是中序遍历树的过程。[1] 参考资料 [1] Oracle递归函数[引用日期2015-11-16] |
|
|
来自： 新用户15472188 > 《待分类》
