原始递归函数
书籍:逻辑百科辞典
由初始函数出发，经有穷次使用复合运算和原始递归运算而得到的函数。
在一般文献中，多取以下的函数为初始函数：
零函数 O(x)=0
后继函数 S(x)=x+1
对每个正整数n，j(1≤j≤n)的射影函数：
(x，…，x)=x．
严格地说，就是：
(1)初始函数都是原始递归函数；
(2)如果m元函数f和n元函数g，…，g都是原始递归的，则由它们复合而得的n元函数
f(g(x，…，x)，…，g(x，…，x))
也是原始递归函数；
(3)如果n元函数f和n+2元函数g都是原始递归的，则由它们经原始递归运算而得到的n+1元函数h：
也是原始递归函数。
原始递归函数都是递归全函数。
在常见的数论函数中，只要是全函数，基本上都是原始递归函数。例如：
常函数 c
恒同函数 x
加函数 x+y
乘函数 x·y
绝对差 ｜x－y｜
阶乘 x!
符号函数sg(x)=｛1 当x＞0
0 当x=0
反符号函数(x)=｛1 当x=0
0 当x＞0等等。
减函数x－y，商函数［y／x］都不是全函数，因而都不是原始递归的，但它们的补全函数
仍都是原始递归函数。