递归函数是数论函数的一种，其定义域与值域都是自然数集，只是由于构作函数方法的不同而有别于其他的函数。最简单又最基本的函数有三个：零函数O(x)=0(其值恒为0)，射影函数，后继函数S(x)=x+1，它们合称初始函数。要想由旧函数作出新函数，必须使用各种算子。在数理逻辑和计算机科学中，递归函数或μ-递归函数是一类从自然数到自然数的函数，它是在某种直觉意义上是"可计算的"。事实上，在可计算性理论中证明了递归函数精确的是图灵机的可计算函数。

数论函数的一种,其定义域与值域都是自然数集,只是由于构作函数方法的不同而有别于其他的函数。处处有定义的函数叫做全函数，未必处处有定义的函数叫做部分函数。最简单又最基本的函数有三个:零函数O(x)=0(其值恒为0);射影函数；后继函数S(x)=x+1。它们合称初始函数。要想由旧函数作出新函数，必须使用各种算子。
代入（又名复合或叠置）是最简单又最重要的造新函数的算子，其一般形状是：由一个m元函数ƒ与m个n元函数 g₁,g₂,…,g_m 造成新函数 ƒ (g₁(x₁,x₂,…,x_n)，g₂(x₁,x₂,…,x_n),…,g_m(x₁,x₂，…，x_n)),亦可记为ƒ(g₁，g₂,…,g_m)(x₁，x₂,…,x_n)。另一个造新函数的算子是原始递归式。具有n个参数u₁，u₂,…,u_n的原始递归式为：

具有一个参数的原始递归式可简写为：

其特点是，不能由g、h两函数直接计算新函数的一般值ƒ(u,x),而只能依次计算ƒ(u,0)，ƒ(u,1)，ƒ(u,2)，…；但只要依次计算，必能把任何一个ƒ(u,x)值都算出来。换句话说只要g,h为全函数且可计算，则新函数f也是全函数且可计算。
由初始函数出发，经过有限次的代入与原始递归式而作出的函数叫做原始递归函数。由于初始函数显然是全函数且可计算，故原始递归函数都是全函数且可计算。通常使用的数论函数全是原始递归函数，可见原始递归函数是包括很广的。但是W.阿克曼证明了，可以作出一个可计算的全函数，它不是原始递归的。经过后人改进后，这个函数可写为如下定义的阿克曼函数：

容易看出,这个函数是处处可计算的。任给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｜）、乘、算术除、叠加Σ、叠乘П而得的函数组成的类。
波兰人A.格热高契克把原始递归函数类按定义的复杂程度来分类，称为格热高契克分层或波兰分层。
要把递归函数应用于谓词，首先要定义谓词的特征函数。谓词R(x,y)的特征函数是

称谓词R 是递归谓词，若R 的特征函数是递归函数；称自然数子集A为递归集,若谓词x∈A是递归谓词。有了上述定义，就可以用递归函数来处理递归谓词和递归集。为了处理N×N（其中N 为自然数集）的子集，就要建立配对函数,所谓配对函数通常是指由N×N 到N 的一个函数ƒ(x，y)与它的逆函数g₁(z)，g₂(z)。它们都满足以下关系。

一个函数在它的函数体内调用它自身称为递归调用。这种函数称为递归函数。这对于程序员来说，通常有很高的实用价值，常用来将复杂的问题分解为简单的并相同的情况，反复做这种处理直到问题解决。

用递归函数与不用递归函数的区别

示例一：使用静态变量

示例二：使用递归函数和循环实现字符串逆转排列

递归函数很多时候我们可以循环替代，建议当我们不能用循环替代时再用，因为用循环我们更容易理解，更不容易出错。

php递归函数 php支付递归函数，递归函数就是调用自己本身，这些函数特别适用于浏览动态数据结构，例如树和列表。
几乎没有web应用程序要求使用复杂的数据结构

这个程序清单中实现两个函数，这两个函数都可以相反的顺序打印字符串的内容

函数reversr_r是通过递归实现的，而函数reverse_i()是通过循环实现的

递归函数即自调用函数，在函数体内部直接或者间接的自己调用自己，即函数的嵌套调用是函数本身。通常在此类型的函数提之中会附加一个条件判断叙述，以判断是否需要执行递归调用，并且在特定的条件下终止函数的递归调用动作，把目前流程的主控权交回到上一层函数来执行。以此，当某个执行递归调用的函数没有附加条件判断叙述时，可能会造成无限循环的错误情形。

函数递归调用最大的好处在于可以精简程序中的复杂重复调用程序，并且能以这种特性来执行一些较为复杂的运算动作。例如，列表、动态树形菜单及遍历目录等操作。相应的非递归函数虽然效率高，但却比较难编程，而且相对来说可读性差。现代程序设计的目标主要是可读性好。随着计算机硬件性能的不断提高，程序在更多的场合优先考虑可读而不是高效，所以，鼓励用递归函数实现程序思想。

一个简单的递归调用实例如下所示：

该程序执行后输出如下的结果：

找到结果中后半部分的数字正向顺序输出的原因

说明：在上面的实例中声明了一个 test()函数，该函数需要一个整型的参数。在函数外面通过传递整数 10 作为参数调用 test()函数。在 test()函数体中，第一条代码输出参数的值和一个空格。然后判断条件是否成立，成立则调用自己并将参数减 1 再次传入。开始调用时，它是外层调内层，内层调更内一层，直到最内层由于条件不允许必须结束。最内存结束了，输出 <--------> 作为分界符，执行调用之后的代码输出参数的值和空格，它就会回到稍外一层继续执行。稍外一层在结束时，退回到在稍外一层继续执行，层层推出，直到最外层结束。执行完成以后的结果就是我们上面看到的结果。

树型菜单在很多桌面应用系统中都有非常广泛的应用，其主要优点是结构清晰，利于使用者非常清楚的知道目前自己所在的位置。但在web上树型菜单的应用因为没有理想的现成组件可以拿过来直接使用，所以一般的情况下，程序员主要是通过JavaScript来实现一些简单的树型结构菜单，但这些菜单往往都是事先定好各菜单项目，以及各菜单项目之间的层次关系，不利于扩充，一旦需要另一个菜单结构时，往往还需要重新编写，因此使用起来不是很方便。

    经过对函数递归的研究，我发现这种树型菜单可以通过递归函数，使树型菜单的显示实现动态变化，并没有级数的限制。下面就是我用php,MySQL,JavaScript写的一个动态树型菜单的处理代码，如果大家有兴趣的话，就和我一起来看看我是如何实现的吧：）

    首先，我们需要一个数据库，在这个数据库中，我们建立以下一张表：

CREATE TABLE menu (
id tinyint(4) NOT NULL auto_increment,
parent_id tinyint(4) DEFAULT \\'0\\' NOT NULL,
name varchar(20),
url varchar(60),
PRIMARY KEY (id)
);

    这张表中
    id 为索引
    parent_id 用来保存上一级菜单的id号，如果是一级菜单则为0
    name 为菜单的名称，也就是要在页面上显示的菜单内容
    url 如果某菜单为末级菜单，则需要指定该连接的url地址，这个字段就是用来保存此地址的，其他非末级菜单，该字段为空