[科普中国]-递归函数

定义

一种计算过程，如果其中每一步都要用到前一步或前几步的结果，称为递归的。用递归过程定义的函数，称为递归函数，例如连加、连乘及阶乘等。凡是递归的函数，都是可计算的，即能行的1。

古典递归函数，是一种定义在自然数集合上的函数，它的未知值往往要通过有限次运算回归到已知值来求出，故称为“递归”。它是古典递归函数论的研究对象1。

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

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

一个直接的例子//代码1void func(){//...if(...)func();lse//...}条件一个含直接或间接调用本函数语句的函数被称之为递归函数，在上面的例子中能够看出，它必须满足以下两个条件：

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。

我们以下考虑的函数都是从自然数到自然数的函数。

我们先定义几个初等函数

(1)零函数 Z(x)=0;

(2)后继函数 S(x)=x+1;

(3)广义幺函数 U1n(x1，…xn)=xi;

显然，上面这些函数都是能行可计算的。

再介绍几个将函数变换为函数的算子。

(1)复合算子 设f是n元函数，g1…gn是m元函数，复合算子将f，g1…gn变换成为如下的m元函数h：

h(x1…xm)=f1g1(x1，…xm)，…gn(x1，…xm))

(2)递归算子 设f是n元函数 (≥0)，g是n+2元函数，递归算子将f，g变换成满足下列条件的h+1元函数h：

h(x1，…，xn，0)=f(x1，…xn)

h(x1，…xn，y+1)=g(x1，…xn，y，h(x1，…xn))

(3)μ一算子，设f是n+1元函数，如果存在y，使f(x1，…xn，y)=0，我们以μyf(x1…xny)表示这样的y中的最小者，如果使f(x1…xny)=0的y不存在，我们说μyf(x1，…xny)无定义。μ-算子将n+1元函数f变换成下面的几元函数h

h(x1，…xn)=μyf(x1…xny)

注意，μ算子可以将一个全函数变换成一个部分函数(即在自然数的某个子集上有定义的函数)。

可以看出，上述所有算子都是将能行可计算函数变换为能行可计算函数。

所谓递归函数类便是包含零函数、广义幺函数，并在复合算子、递归算子，μ-算子下封闲的最小函数类。

容易相信，任何递归函数都是能行可计算的。反过来，是否存在直观上能行可计算的，但不是递归的函数呢?人们直到现在还没有发现这样的函数。相反，人们证明了，现已遇到的直观上能行可计算的函数都是递归函数。进一步，人们还证明了，递归函数类与其他的一些刻画能行可计算函数的方法产生的函数类是完全一致的，这些事实促使车尔赤(Church)提出了他的著名的论点：

递归函数类与直观能行可计算函数类是重合的。

这个论点已被大多数递归论学者所接受。

例子【pascal语言】

//使用VB代码格式，实际为Pascalfunctiondo(x:integer);beginifx1thenexit(do(x-1)+10)end;