作者：张寅生

1、广义递归函数家族

所谓的递归函数就是广义递归函数，其分类见表1：

                                  表1  递归函数的分类

        明白了m-递归函数明白了递归函数的核心原理（图灵机的转移函数即对应m-递归函数）。因此这里略去“阿克曼递归函数”和“其他递归函数”。

2  原始函数

构成原始递归函数的“原料”是原始函数，有三种：常值函数、后继函数和投影函数。

常值函数（将定义域内某元素映射为一个常值）；

后继函数（将定义域内某元素映射为它的下一个数）；

投影函数（将定义域内某元素映射为一个变量）。

3  递归函数的构造方法

由上述3个原始函数构造更为复杂的递归函数的方法有两种：复合方法、递归方法。

复合方法：已知函数h（y ₁，…，y_k），g₁（x₁，…，x_n），g₂（x₁，…，x_n），…，g_k（x₁，…，x_n），那么，复合函数是

        f（x₁，…，x_n）= h（g₁（x₁，…，x_n），g₂（x₁，…，x_n），…，g_k（x₁，…，x_n））

 即f是通过h和g的复合得到的，写作f=h￮g。

   直观的说，复合就是把n个g系列的原始函数，代入另一个原始函数h里的n个自变量之中：

递归方法：已知函数g（x₁，…,x_n），h（x₁，…，x_n,y, z），则递归函数 f:

f（x₁，…，x_n，0）= g（x₁，…，x_n）                

f（x₁，…，x_n，y+1）= h（x₁，…，x_n,y, f（x₁，…，x_n，y））  

是由h和g经过递归得到的。

       所说的“递归方法”应理解为构造递归函数的多种结构方式的一种（另一种是“复合方法”），因而不是递归函数的所有构造方式，所以“递归方法”全称应该是“通过递归方式构造递归函数的一种方法”。

递归方法需要用3个原始函数（“砖石”）g，f，h，其中，g，h是中间过程的“过渡产品”，f才是所需要的最终结果（我们要盖的“房子”！）。这里有个窍门：递归分为两个部分（上下两行）。f的变量的个数在两个部分都是相同的，即都是n+1个；但是g比f的变量的个数少一个，即n个，而h比f的变量的个数多一个，即n+2个。这样的设计结果是基于这样的考虑，假设f不容易得到，但是带有变量初始值的函数一般是容易得到的，得到的方法是从一个比f具有更少变量的函数g来计算带有变量初始值的f，这就是从简单到复杂的思想。h函数的变量最然必f的变量多两个，但是通过上一步的运算，增补的这两个函数的自变量y, f（x₁，…，x_n，y）都是可得到的了。

“递归”，在本意上和字面上理解，就是“一步一步地回去”。“递”也就是“分步骤地”，可以想象一个递次就是梯子的一个格；“归”就是“回去”。------什么东西回到哪里去？是目标函数值回到这个函数自身的自变量里去了！这似乎很奇怪：我们目标是求一个函数的值，既然得到了，为什么又作为自变量输入到它自身的一个自变量里去？原因就是在“递次”里面：在前一个递次，函数值得到了，但是下一个递次的函数值我们不知道；不仅函数值我们不知道，函数值里面的变量也不知道，于是我们用本递次的函数值嵌入到这个函数之中，作为变量之一，去求解下一递次的函数值。

考察递归方式形成递归函数的形成过程。

在第一个步骤，也就是初始步骤。将初始值的f表达式带入函数h的最末一个变量（使用了复合方法），同时，函数f的值作为 h的变量被写入 h，得到了f（x₁，…，x_n，y+1）。

在第二个步骤，也就是f往返过程。通过f(y+1，…)向h的回归的得到的f(y+2，…)，f(y+2，…)向h的回归将得到f(y+3，…)等等，直至达到预期的步骤和结果。每一个循环就是一个递次的回归。

我们有了用于构造递归函数的原料（原始函数）和方法（复合方法和递归方法），就可以构造原始递归函数。

        原始递归函数：原始函数或者原始函数经过复合或递归得到的函数称为原始递归函数。

 “原始递归函数”是数学家构造的首个递归函数。之所所称为“原始的”，因为构造它所使用的函数是“原始函数”。作为名词，“原始递归函数”的概念是哥德尔1931年提出的^[1][2]。但是这一函数形式本身是斯克伦于1923年提出的^[3]。原始递归函数是实现通过函数构造递归函数进而求解递归函数的最初的尝试。

例1    自然数的加法是原始递归函数。

                                                  x+0=x

                                                 x+(y+1)=(x+y)+1

通用的自然数加法函数可以写为

  add (x,0)=P¹₁(x)

                                                add (x,y+1)=S(P¹₃(x,y,add(x,y)))

 其中：S是后继函数；P是投影函数；add 是加法函数。

在此例中，S，P是原始函数，我们假设它们是已经知晓如何计算的；add函数是我们想要求的。我们虽然暂时不知道它，但是通过S，P得知了add 的初始值，并通过S，P和add 递次回归，就得出了add 的目标值。把add函数通过递归的方式构造，似乎觉得多此一举，因为i额我们有关于所有自变量和因变量的映射规则，那为什么要递归呢？要知道递归函数的目的是逐步获得目标函数f的值。因为我们假设对于函数add除初值外的运算法则我们是不知道的才对add进行递归运算。

例2  证明乘法函数是递归函数。

证明：

                                          x×0=0

                                x×(y+1)=x+(x×y) 

或者：

                                   Mul (x,0)=P¹₁(x)

                           Mul (x,y+1)=add(x,Mul(x,y))

通过递归进行计算的基本目的是使计算更具有普适性，即能够计算更多的数和函数，进而可求解更为广泛的问题。对于像z=x+y等许多简单的初等函数，给定x和y的常元赋值，函数就通过直接的计算得到了。这里，“直接的计算”是指不再需要其他的函数。但是，在许多情况下，x和y是不能或不容易显式得到的，也需要函数计算，甚至逐次计算，在这种情况下，函数值z就不是直接计算了，而是通过其他函数得到x和y的一次赋值，再进行针对这次赋值的z值的计算。因此，z不是通过一个函数计算出来的，并且不是一次计算得出的。简单地说，这种分函数、分步计算，即通过逐次计算子函数将其结果输入变元再逐次计算函数的办法就是原始递归的办法。

加法和乘法具有递归性，那么，它们的反运算如何呢？显然，自然数逆运算可能涉及两个难题，一个难题是可能产生负数和小数，即逆运算的结果可能不封闭于定义域，也就是说，计算的结果跑出了自然数的范围。这样，如果要求定义域和像（值域）是重合的，就必须扩大定义域的范围，使得反函数（逆运算）有定义，由此必须应用部分函数的概念定义递归函数，使得函数的定义域从处处有定义的全函数的定义域，扩大到原来没进行定义的数域，以满足反函数处处有定义（使反函数至少是全函数）。为此定义了“部分递归函数”。另外一个难题是逆运算可能产生无限循环，如1/3，。如何机械地计算一个无限循环的值？图灵给出的解决方法是算出一个近似值替代无限循环的值本身，例如，将0.333和0.414作为1/3，的（近似）计算结果。这样，计算的结果会因位数的长短不同而有很多。如果用极小值函数确定一个极小的误差（上确界）e，就可以确定一个最近似的值，例如，对于e₁＜0.1，可以得到1/3的一个近似值0.3；e₂＜0.01，可以得到0.33；等等。

此外，不只无限循环要求无穷步骤的计算，还有一些情况如无穷变元计算也可能导致无穷计算，如三角函数的反函数arcsinq，原函数sinq的定义域q也可以是无穷的。这样也需要极小值的函数以确定一个极小的q，以此为起点枚举良序中逐步大的q。

 极小值函数（最小值函数；m-算符操作，m-算符，m-算子）：设g(t，x₁，…，x_n)是一个全函数，定义f（x₁，…，x_n）如下： 

f（x₁，…，x_n）=mt[g(t，x₁，…，x_n)=0]

                                                   =min{t| g(t，x₁，…，x_n)=0}            

称f（x₁，…，x_n）是g(t，x₁，…，x_n)通过对t取极小值运算得到的函数，即t有多个值，其中的极小值mt即f（x₁，…，x_n）的取值（记作mt[g(t，x₁，…，x_n)=0]，也就是满足特征方程g(t，x₁，…，x_n)=0的多个t中的最小的t。因此可以将mt理解为在h(x₁，…，x_n)=t中搜索极小的t的操作（h的特征方程是g）。

对于逆函数的运算，可将g理解为计算f的反函数（逆运算函数）f ^–（或者递归得到f ^–的原始函数）的特征函数。

m算符更为直观的解释定义是 

f（x₁，…，x_n）=最小的t   满足

g(t，x₁，…，x_n)=0         如果存在最小值t

g(t，x₁，…，x_n)=1         如果不存在最小值t

     这样就可以定义两个函数T₁和T₂，当T₁ 运算f并找到一个最小的t，即mt，使得f ^–的特征函数g=0，在此状态下，T₂计算f ^–(t)。

 m-递归函数、m-部分递归函数：原始递归函数或者原始递归函数经过复合或递归，或通过取极小值得到的函数，称为m-递归全函数（如果是指处处有定义的递归函数）；如果函数取值不加限制（可以不必是完全的），那么，就得到m-部分递归函数 。

可见，m-递归函数由于定义了逆运算的定义域以及在无穷计算中的有穷近似值，因此使得递归函数的定义域扩大到了实数域。

4  递归函数的通俗解释

无论是m-部分递归函数还是原始递归函数，它们就像一个序列的门，每个递次的目标函数都是一个门，但是我们不能一次将序列的门的钥匙都拿到手，但是通过递次地输入和获得递增的自变量并通过分解函数计算不同递次的目标函数，就像开一个们，才拿到了下一个门的钥匙，这是数学归纳法的的精神的实现。

如果计算4+6，运用x+0=x和x+(y+1)=(x+y)+1进行递归，计算过程是：

 4+0=4；

4+1=(4+0)+1；

4+2=(4+1)+1；

4+3=(4+2)+1；

4+4=(4+3)+1；

4+5=(4+4)1；

4+6=(4+5)+1

即为算出4+6，要逐次通过4+0算出4+1；通过4+1算出4+2；……算出4+6，即算下一步要通过得到前一步的结果来实现。而加法的通常的计算无需从4+0算到4+5再计算5+6在计算5+6。这就是递归计算的本质。用通俗说法描述这一过程是，用前一个匣子里的钥匙开后一把锁。这一使得，当我们没有所有自变量取值的运算结果清单（没有所有自变量映射其函数值的“映射法则”，也就是说不会有类似于x=4，y=1,2,3,4,5,6时的全函数的加法器，只有类似于加1，即实现一个步长函数运算的加法器）时可以逐一分部获得前步计算结果逼近并实现最终的计算。也可以把递归函数比作上楼梯。在不能一下子上到楼层顶上的情况下，就每次登一阶楼梯台阶，在这个台阶基础上，再登下一阶台阶，每个台阶都以前一台阶为基础……最后登顶。

参考文献：

[0]张寅生. 计算理论解析，清华大学出版社，2015年。

[1]Kurt Godel.On Formally Undecidable Propositionsof Principia Mathematica and Related SystemI.From Frege to Godel,Harvard University Press,pp.592-.617.

[2]科特·哥德尔著，张寅生译：《论〈数学原理〉及其相关系统的形式不可判定命题（I）》/张寅生.证明方法与理论，国防工业出版社，2015年。

[3]Thoralf Skolem.Thefoundation of elementary arithmetic established by means of the recursion modeof thought,without the use of apparent variables ranging over infinite domains./From Frege to Godel//A Source Book inMathematical Logic,1879~1931.Havard University Press,1977:302~333.

[4]Stephen Kleene（1952）Introduction to Metamathematics.Walters-Noordhoff & North-Holland, with corrections (6th imprint 1971);Tenth impression 1991.

[5]Bobert Soar.Computebility and Recursion,Bulletin of Symbolic Logic,Vol.2,Num.3,1996:284-321.