递归函数是 数论 函数的一种，其定义域与 值域 都是 自然数 集，只是由于构作函数方法的不同而有别于其他的函数。最简单又最基本的函数有三个：零函数O(x)=0(其值恒为0)，射影函数，后继函数S(x)=x+1，它们合称初始函数。要想由旧函数作出新函数，必须使用各种 映射 。
在 数理逻辑 和 计算机科学 中，递归函数或μ-递归函数是一类从自然数到自然数的函数，它是在某种直觉意义上是"可计算的"。事实上，在可计算性理论中证明了递归函数精确的是 图灵机 的可计算函数。
定理定义
数论 函数的一种，其定义域与 值域 都是 自然数 集,只是由于构作函数方法的不同而有别于其他的函数。处处有定义的函数叫做全函数，未必处处有定义的函数叫做部分函数。最简单又最基本的函数有三个：零函数 O ( x )=0(其值恒为0);射影函数 ；后继函数 S ( x )= x +1。它们合称初始函数。要想由旧函数作出新函数，必须使用各种 映射 。
代入（又名复合或叠置）是最简单又最重要的造新函数的算子，其一般形状是：由一个m元函数 ƒ 与m个 n 元函数 g 1, g 2,…, g m 造成新函数 ƒ ( g 1( x 1, x 2,…, xn )， g 2( x 1, x 2,…, xn ),…, g m( x 1, x 2，…， xn )),亦可记为 ƒ ( g 1， g 2,…, g m)( x 1， x 2,…, xn )。另一个造新函数的算子是原始递归式。具有 n 个参数 u 1， u 2,…, un 的原始递归式为：
具有一个参数的原始递归式可简写为：
递归函数
其特点是，不能由 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 1( z )， g 2( z )。它们都满足以下关系：
可以构造许多原始递归的配对函数。
递归函数也可以用来处理符号串。处理的办法是对符号及符号串配以 自然数 。这方法是 库尔特·卡塞雷斯 开始引进的，因此称为哥德尔配数法。例如，在要处理的符号系统｛ α 1， α 2， α 3,…｝中，可以用 奇数 1，3，5，7，…作为 α 1, α 2， α 3， α 4，…的配数，符号串 以 为其配数，其中 P s是第 s 个素数, nij 是 αij 的配数。这种配数称为哥德尔配数。有了哥德尔配数法，就可以用递归函数来描写、处理有关符号串的谓词了。
运用
(一)
目的：将1号和2号从A移到B
调用函数：hanoi(2,'A', 'C', 'B')。
在 hanoi (2,'A', 'C', 'B')中递归调用如下：
A-->C---- 河内 (1,'A', 'B', 'C')
A-->B----hanoi(1,'A', 'C', 'B')
C-->B----hanoi(1,'C', 'A', 'B')
(二)
目的：将3号从A移到C
调用函数：hanoi(1,'A', 'B', 'C')
A-->C
(三)
目的：将1号和2号从B移到C
调用函数： hanoi (2,'B', 'A', 'C')
在 hanoi (2,'B', 'A', 'C')中递归递归如下：
B-->A---- 河内 (1,'B', 'C', 'A')
B-->C----hanoi(1,'B', 'A', 'C')
A-->C---- hanoi (1,'A', 'B', 'C')
总共调用了7次函数，
只要hanoi()的第一个参数大于1，它就会在内部调用自身3次，“直到第一个参数＝1，然后调用printf()”。
hanoi(n, ...)调用hanoi(1, ...)的次数为2的n次方减去一。
pascal 语言
【pascal语言】
函数 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<<"\n输入一个正整数:";
cin>>N;
cout<<"\n 1+2+...+"<<N<<"的结果是:"<<fn(N)<<"\n";
} //递归函数的定义
int fn(int i)
{
if(i==1)
回车键 1;
else
return i+fn(i-1);
}
正确写出
如何快速正确的写出递归函数？写一个递归函数是非常程式化的东西，只要按照一定的规则来写，就可以很容易地写出递归函数。写递归函数有三步：
①写出迭代公式；
②确定递归终止条件；
③将①②翻译成代码。以求n！为例：
①写出迭代公式：n！的迭代公式为
②确定递归终止条件：1！＝1就是递归终止条件
③将①②翻译成代码：将迭代公式等号右边的式子写入 回车键 语句中，即return （fact（n-1））*n;long fact（int n） { if （n==1） return 1; return （fact（n-1））*n; } 下面再举一个例子，希望能帮助大家进一步体会这一原则
写一个函数，求：f（n）= 陈氏定理 +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） 回车键 1; return （Sum（n-1））+n; }
Oracle数据库 用法
Oraclestart with connect by 用法
oracle 中 connect by prior 递归算法
Oracle中start with...connect by prior子句用法 connect by 是结构化查询中用到的，其基本语法是：
select ... from tablename start with 条件1
connect by 条件2
where 条件3;
例：
select * from table
start with org_id = 'HBHqfWGWPy'
connect by prior org_id = parent_id;
简单说来是将一个树状结构存储在一 张表 里，比如一个表中存在两个字段:
org_id,parent_id那么通过表示每一条记录的parent是谁，就可以形成一个树状结构。
用上述语法的查询可以取得这棵树的所有记录。
其中：
条件1 是根结点的限定语句，当然可以放宽限定条件，以取得多个根结点，实际就是多棵树。
条件2 是连接条件，其中用PRIOR表示上一条记录，比如 CONNECT BY PRIOR org_id = parent_id就是说上一条记录的org_id 是本条记录的parent_id，即本记录的父亲是上一条记录。
条件3 是过滤条件，用于对返回的所有记录进行过滤。
简单介绍如下：
早扫描树结构表时，需要依此访问树结构的每个节点，一个节点只能访问一次，其访问的步骤如下：
第一步：从根节点开始；
第二步：访问该节点；
第三步：判断该节点有无未被访问的子节点，若有，则转向它最左侧的未被访问的子节，并执行第二步，否则执行第四步；
第四步：若该节点为根节点，则访问完毕，否则执行第五步；
第五步：返回到该节点的父节点，并执行第三步骤。
总之：扫描整个树结构的过程也即是中序遍历树的过程。