递归函数

对于某一函数f（x），其定义域是集合A，那么若对于A集合中的某一个值X0，其函数值f（x0）由f（f（x0））决定，那么就称f（x）为递归函数。

介绍(定义 条件)

计算(正确写出 例子)

介绍

定义

在数学上，关于递归函数的定义如下：对于某一函数f(x)，其定义域是集合A，那么若对于A集合中的某一个值X0，其函数值f(x0)由f(f(x0))决定，那么就称f(x)为递归函数。

在编程语言中，把直接或间接地调用自身的函数称为递归函数。函数的构建通常需要一个函数或者一个过程来完成。

在数理逻辑和计算机科学中，递归函数或μ-递归函数是一类从自然数到自然数的函数，它是在某种直觉意义上是"可计算的" 。事实上，在可计算性理论中证明了递归函数精确的是图灵机的可计算函数。递归函数有关于原始递归函数，并且它们的归纳定义(见下)建造在原始递归函数之上。但是，不是所有递归函数都是原始递归函数 — 最著名的这种函数是阿克曼函数。

其他等价的函数类是λ-递归函数和马尔可夫算法可计算的函数。

条件

一个含直接或间接调用本函数语句的函数被称之为递归函数，它必须满足以下两个条件：

1） 在每一次调用自己时，必须是（在某种意义上）更接近于解；

2） 必须有一个终止处理或计算的准则。

例如：

梵塔的递归函数

void hanoi （int n, char x, char y, char z）

{

if （n==1）

move（x, 1, z）；

else {

hanoi（n-1, x, z, y）；

move（x, n, z）；

hanoi（n-1, y, x, z）；

}

}

计算

数论函数的一种，其定义域与值域都是自然数集，只是由于构作函数方法的不同而有别于其他的函数。处处有定义的函数叫做全函数，未必处处有定义的函数叫做部分函数。最简单又最基本的函数有三个：零函数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的原始递归式为：（图1）具有一个参数的原始递归式可简写为：（图2）其特点是，不能由g、h两函数直接计算新函数的一般值？（u,x），而只能依次计算？（u,0），？（u,1），？（u,2），…；但只要依次计算，必能把任何一个？（u,x）值都算出来。换句话说?只要g,h为全函数且可计算，则新函数f也是全函数且可计算。

由初始函数出发，经过有限次的代入与原始递归式而作出的函数叫做原始递归函数。由于初始函数显然是全函数且可计算，故原始递归函数都是全函数且可计算。通常使用的数论函数全是原始递归函数，可见原始递归函数是包括很广的。但是W.阿克曼证明了，可以作出一个可计算的全函数，它不是原始递归的。经过后人改进后，这个函数可写为如下定义的阿克曼函数：（图3）容易看出，这个函数是处处可计算的。任给m,n的值，如果m为0，可由第一式算出；如果m不为0而n为0，可由第二式化归为求g（m,1）的值，这时第一变目减少了；如果m，n均不为0,根据第三式可先计算g（m,n-1），设为α，再计算g（m-1,α），前者第二变目减少（第一变目不变），后者第一变目减少。极易用归纳法证得，这样一步一步地化归，最后必然化归到第一变目为0，从而可用第一式计算。所以这个函数是处处可计算的。此外又容易证明，对任何一个一元原始递归函数？（x），永远可找出一数α使得？（x）<g（α，x）。这样，g（x,x）+1便不是原始递归函数，否则将可找出一数b使得g（x,x）+1<g（b,x）。令x=b，即得g（b,b）+1<g（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<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|）、乘、算术除（图2）、叠加Σ、叠乘П而得的函数组成的类。

波兰人A.格热高契克把原始递归函数类按定义的复杂程度来分类，称为格热高契克分层或波兰分层。

要把递归函数应用于谓词，首先要定义谓词的特征函数（图6）。谓词R（x,y）的特征函数是（图4）：称谓词R 是递归谓词，若R 的特征函数是递归函数；称自然数子集A为递归集，若谓词x∈A是递归谓词。有了上述定义，就可以用递归函数来处理递归谓词和递归集。为了处理N×N（其中N 为自然数集）的子集，就要建立配对函数，所谓配对函数通常是指由N×N 到N 的一个函数？（x，y）与它的逆函数g1（z），g2（z）。它们都满足以下关系：（图5）可以构造许多原始递归的配对函数。

递归函数也可以用来处理符号串。处理的办法是对符号及符号串配以自然数。这方法是K.哥德尔开始引进的，因此称为哥德尔配数法。例如，在要处理的符号系统{α1，α2，α3,…}中，可以用奇数1，3，5，7，…作为α1,α2，α3，α4，…的配数，符号串（图7）以（图8）为其配数，其中Ps是第s个素数，nij是αij的配数。这种配数称为哥德尔配数。有了哥德尔配数法，就可以用递归函数来描写、处理有关符号串的谓词了。

正确写出

如何快速正确的写出递归函数？写一个递归函数是非常程式化的东西，只要按照一定的规则来写，就可以很容易地写出递归函数。写递归函数有三步：

①写出迭代公式；

②确定递归终止条件；

③将①②翻译成代码。

以求n！为例：

①写出迭代公式：n！的迭代公式为

②确定递归终止条件：1！=1就是递归终止条件

③将①②翻译成代码：将迭代公式等号右边的式子写入return语句中，即return （fact（n-1））*n;

将1！=1翻译成判断语句：if（n==1） return 1;

按照先测试，后递归的原则写出代码。

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;

}

例子

【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<<"\输入一个正整数:";

cin>>N;

cout<<"\ 1+2+...+"<<N<<"的结果是:"<<fn(N)<<"\";

}

//递归函数的定义

int fn(int i)

{

if(i==1)

return 1;

else

return i+fn(i-1);

}