递归函数的介绍

1. 递归函数的介绍

在数理逻辑和计算机科学中，递归函数或μ-递归函数是一类从自然数到自然数的函数，它是在某种直觉意义上是可计算的 。事实上，在可计算性理论中证明了递归函数精确的是图灵机的可计算函数。递归函数有关于原始递归函数，并且它们的归纳定义(见下)建造在原始递归函数之上。但是，不是所有递归函数都是原始递归函数 — 最著名的这种函数是阿克曼函数。其他等价的函数类是λ-递归函数和马尔可夫算法可计算的函数。 一个含直接或间接调用本函数语句的函数被称之为递归函数，在上面的例子中能够看出，它必须满足以下两个条件：1） 在每一次调用自己时，必须是（在某种意义上）更接近于解；2） 必须有一个终止处理或计算的准则。例如：梵塔的递归函数  //Cvoid 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);}}阶乘的递归函数，公式如下：  //C++int Factorial(int n){if(n==0||n==1)return 1;elsereturn n * Factorial(n-1)}

2. 递归函数的介绍

编程语言中，函数Func(Type a,……)直接或间接调用函数本身，则该函数称为递归函数。递归函数不能定义为内联函数。在数学上，关于递归函数的定义如下：对于某一函数f(x)，其定义域是集合A，那么若对于A集合中的某一个值X0，其函数值f(x0)由f(f(x0))决定，那么就称f(x)为递归函数。

3. 函数递归

讲解吗：
那给你讲一下。
比如  求一个数的阶乘  n！ 在数学上这个是要一步步算的，怎么算呢，这样
  n！=1*2*3*4*5*...*n  也就是从1乘到n  但是你会发现  从1乘到n-1是什么呢，是不是（n-1）！  这就有意思了，要求的n！势必要先算到（n-1）！然后再乘上一个n就得到n！，那也就是说n！=（n-1）！*n。这更有意思了，本来我要求n！，反而在展开中也出现了和我n！形状类似的（n-1）！，这是怎么回事呢。这就是如果我假定有一个函数是用来求n！，那么函数的内部是需要用到（n-1）！*n表达式的。可是我现在就是在写这个函数的啊，怎么函数里面居然提前用到了这个函数。现在你明白了吗，这就是函数的递归。

简单点，就是求一个问题的时候，需要依赖这个问题的另一个量的结果的这么个问题。
如求n！，需要依赖知道n-1的阶乘。可是（n-1）！其实与n！原理一样，都是那么个求法，只不过问题的规模量不同而已，一个是n，一个是n-1.

4. 递归函数问题

解题步骤：

1,ack(1,n)=ack(0,ack(1,n-1))+1=ack(1,n-1)+1;

由递推式得：ack(1,n)=n+1;

2，ack(2,n)=ack(1,ack(2,n-1))=ack(2,n-1)+2; 
 //递推式

  由递推式得：ack(2,n)=2n+3;

3,ack(3,n)=ack(2,ack(3,n-1))=2*ack(3,n-1)+3; //递推式

  即：ack(3,n)+3=2(ack(3,n-1)+3)

  得: ack(3,n)+3=(ack(3,1)+3) * 2^(n-1);

  又ack(3,1)=2ack(3,0)+3

    ack(3,0)=a(2,1)=5

  所以ack(3,1)=13;

  所以 ack(3,n)=2^(n+3) -
 3;

所以：ack(3,3)=61;

PS：
这个是著名的Ackerman（阿克曼）函数，典型的非原始递归的递归函数，m<=3的时候像我上面的递推和计算很简单，但是一旦再大就会很麻烦，甚至计算机会彻底无法计算。
可以参考wiki资料了解相关内容：
http://zh.wikipedia.org/zh-cn/%E9%98%BF%E5%85%8B%E6%9B%BC%E5%87%BD%E6%95%B8

5. 递归论的基本内容

 处处有定义的函数叫做全函数，未必处处有定义的函数叫做半函数或部分函数。最简单、最基本的函数有三个，即①零函数，O(x)=0，其值永为0；②广义幺函数或射影函数，Imn(x1，…，xm) =xn（1≤n≤m）；③后继函数，Sx(=x+1）。这三个函数的合称就叫做本原函数。要想由旧函数而作出新函数，必须使用各种各样的算子以及叠置。叠置又名复合或代入，它是最简单、最重要的构造新函数的方法。其一般形式是：由一个 m元函数 f与 m个 n元函数 g1，g2，… ，gm 而造成新函数f【g1(x1，…，xn),g2(x1，…，xn），…，gm(x1，…，xn）】，后者亦可记为f(g1，…，gm)(x1，…，xn）。最常见的造新函数的算子是原始递归式。其特点是：不能由A、B两函数而直接计算新函数的一般值f(u,x），而只能依次计算f(u,0),f(u,1），f(u,2），…。但只要依次计算，必能把任何一个 f(u,x) 值都算出来。这就是说，只要A、B为全函数且可计算，则新函数f也是全函数且可计算。 由本原函数出发，经过有限次的叠置与原始递归式而作出的函数叫做原始递归函数。由于本原函数是全函数且可计算，故原始递归函数也是全函数且可计算。原始递归函数所涉及的范围很广，在数论中所使用的数论函数全是原始递归函数。阿克曼却证明了一个不是原始递归的可计算的全函数。经过后人改进后，可表述为如下定义的函数：这个函数是处处可以计算的。任给 m,n值，如果m为0，可由第一式算出；如果m不为 0而n为0，可由第二式化归为求g(m,1）的值，这时第一变目减少了，如果m,n均不为0，根据第三式可先计算g(m,n-1）（设为A），再计算g(m-1,A），前者g的第二变目减少而第一变目不变，后者则第一变目减少。这样一步步地化归，最后必然化归到第一变目为0，从而可用第一式计算。此外，对任一个一元原始递归函数f(x），都可找出一数a使f(x)<g(a,x）。这样，g(x,x)+1就不可能是原始递归函数。原始递归式的推广，可得到下列有序递归式或半递归式：它与原始递归式的不同点，在于它不是把 f(u,Sx）的计算化归于f(u,x，）的计算，而是先化归于f(u,g(u,Sx））的计算，然后化归于f【u,g(u,g(u,Sx））】的计算（可写成f(u,g娾Sx）），再化归于f(u,g咺Sx）的计算，等等。如果有一个m使得g嚲Sx =0即函数gu在Sx处归宿于0，那末最后化归的f(u,g嚲Sx）的计算，将由第一式知f(u,0)=A(u），依次逐步倒退便可以计算f(u,x）了。如果任何 m均使得g嚲Sx≠0，即函数gu在Sx处不归宿于0，将导致永远化归下去而得不到结果。这样，不但不能计算 f(u,Sx），而且它本身根本没有定义。由此可见，即使A、B与g是处处有定义且可计算的，而由半递归式所定义的函数未必是全函数，也可能是半函数。但只要有定义的地方，即gu归宿于0的地方，就必能计算。 从本原函数出发经过有限次的叠置与半递归式构成的函数叫做递归半函数或递归部分函数，也叫做半递归函数或部分递归函数。这里所提到的“半”、“部分”不是限制“递归”而是限制“函数”的。如果作出的函数是全函数，即其中的gu是处处归宿于 0的，便叫做递归全函数也叫做一般递归函数。递归半函数的特点是，它可能没有定义从而没有值，但只要有值必然可以计算。一般递归函数的特点是，它必处处有定义而且处处可以计算。当递归半函数没有定义时，一般是不知道的。这样，即使把 f(u,Sx）化归于f(u,gu,Sx），再化归于f(u,gu2Sx），…，如此永远计算下去，也始终得不到其值，并且始终不知道它没有值。但如果另有办法判定递归半函数是否有值，即是否有定义，情况便大不相同。凡是能够判定某个递归半函数是否有值的，该递归半函数叫做潜伏递归函数。对潜伏递归函数永可在有限步内得出其值，或知道它没有值，而与一般递归函数相同。另一个重要的构造新函数的方法是造逆函数，例如由加法造减法，由乘法造除法等。设已有函数f（u,x）（只写一个参数u）就x解方程 f(u,x)=t可得x=g(u,t），这时函数 g 叫做f（作为 x的函数）的逆函数，可记为g(u,t) = f层（t），至于解一般的方程f(u,t,x) =0而得x=g(u,t），可以看作求逆函数，即三元函数f的逆的推广，解方程可以看作使用求根算子，又叫摹状算子。f (u,t,x)=0的最小x根，记为u∝【f(u,t,x) =0】，但当该方程没有根时，则认为u∝【f(u,t,x) =0】，没有定义。因此，即使f(u,t,x）处处有定义且可计算，但使用摹状算子后所得的函数u∝【f(u,t,x) =0】仍不是全函数，可为半函数。且只要它有定义，那就必然可以计算。如果f(u,t,x) 本身就是半函数，则u∝【f(u,t,0) =0】的意义是：当f(u,t,x）可计算且其值为0，而x<n时f(u,t,x）均可计算，且其值非0，则u∝【f(u,t,x) =0】指n。此外的情况均作为无定义看待。例如，f(u,t,x) =0根本没有x根，或者虽然知道有一根为n，但f(u,t,n-1）不可计算，这时u∝【f(u,t,0) =0】都作为没有定义。 由本原函数出发，经过有限次叠置原始递归式与摹状式而构成的函数叫做可摹状函数。可摹状函数一般是部分函数，当摹状算子处处有定义时，它才是全函数。但不管是否全函数，凡可摹状函数有定义的地方都是可计算的。已经证明，可摹状函数与递归半函数是相同的，可摹状的全函数与一般递归函数也是相同的。凡可摹状函数都可以构作一个图林机器（见图林机器理论）计算它，使得当函数有定义时，相应的图林机器必能终止计算并给出其值；当函数没有定义时，相应的机器或者停止并给出没有定义的信号，或者永不停止。由于递归函数可以与其性质这样不同的函数类相等价，因此丘奇和图林同时提出：可计算函数类恰好是递归函数，可计算的半、全函数分别是递归半、全函数。他们的这个论点现已受到数理逻辑学界的一致赞同，并被当作能行性理论的一个基础。

6. 函数递归问题

有用。递归的概念尤其是在编程领域很实用，举个简单的例子：比如你要搜索某个路径下面所有的图片或者音乐文件，那么你就要用到递归，因为你搜索的路径下面既有文件夹又有文件。比如搜某个文件夹下面的文件函数为SearchFile（String path），那么在这个函数实现里面遇到新的文件夹，就得再次调用函数SearchFile（String path），经典的函数递归。

7. 什么是递归函数？

递归式解决逻辑问题的。基本思想是：：把规模大的、较难解决的问题变成规模较小的、易解决的同一问题。规模较小的问题又变成规模更小的问题，并且小到一定程度可以直接得出它的解，从而得到原来问题的解。
C有一个汉诺塔,就是非用递归才能解决的一个问题。
利用递归算法解题，首先要对问题的以下三个方面进行分析： 
一、决定问题规模的参数。需要用递归算法解决的问题，其规模通常都是比较大的，在问题中决定规模大小（或问题复杂程度）的量有哪些？把它们找出来。 

二、问题的边界条件及边界值。在什么情况下可以直接得出问题的解？这就是问题的边界条件及边界值。 

三、解决问题的通式。把规模大的、较难解决的问题变成规模较小、易解决的同一问题，需要通过哪些步骤或等式来实现？这是解决递归问题的难点。

8. 什么是递归函数？举例