原始递归函数

在可计算性理论中，原始递归函数（英语：primitive recursive functions）对计算的完全的形式化而言是形成重要构造板块的一类函数。它们使用递归和复合作为中心运算来定义，并且是递归函数的严格的子集，它们完全是可计算函数。通过补充允许偏函数和介入无界查找运算可以定义出递归函数的更广泛的类。
通常在数论中研究的很多函数，近似于实数值函数，比如加法、除法、阶乘、指数，找到第n 个素数等等是原始递归的（Brainerd and Landweber, 1974）。实际上，很难设计不是原始递归的函数，尽管某些函数是已知的(比如阿克曼函数)。所以，通过研究它们，我们能发现有广泛影响的结论的那些性质。
原始递归函数可以用总是停机的图灵机计算，而递归函数需要图灵完全系统。
原始递归函数的集合在计算复杂性理论中叫做PR。

转换谓词到数值函数

在某些设置中，自然的考虑接受混合了数值和真值{ t= true, f=false } 的参数，或生成真值作为输出的原始递归函数(参见 Kleene [1952 pp.226-227])。这可以通过把真值识别为任何固定方式的数值来完成。例如，通常把真值t 识别为1 和真值f 识别为0。一旦作出这种识别，集合 A 的特征函数，它在文字上返回1 或 0，可以被看作判定一个数是否在集合A 中的谓词。把谓词识别为数值函数的这种方式将假定于本文余下部分。

在整数和有理数上的运算

通过使用哥德尔数，原始递归函数可以被扩展到在其他对象比如整数和有理数上的运算上。如果以标准方式编码整数用哥德尔数，算术运算包括加法、减法、乘法都是原始递归的。类似的，如果以哥德尔数表示有理数，则域运算都是原始递归的。

与递归函数的联系

通过介入无界查找算子可定义更广泛的偏递归函数类。这个算子的使用可以导致偏函数，就是说，对每个参数有最多一个值，但是不同于全函数，不必须对参数有值的关系(参见定义域)。一个等价的定义声称偏递归函数是可以被图灵机就算的函数。全递归函数是对所有输入有定义的偏递归函数。
所有原始递归函数都是全递归的，但不是所有全递归函数都是原始递归的。阿克曼函数 A(m,n)是周知的不是原始递归的全递归函数。原始递归函数有作为使用阿克曼函数的全递归函数的子集的一个特征。这个特征声称一个函数是原始递归的，当且仅当有一个自然数m 使得这个函数可以被总在A(m,n) 或更少步骤内停机的图灵机计算，这里的n 是原始递归函数的参数的总数。

限制

原始递归函数意图紧密对应于我们直觉上可计算函数应该的样子。当然函数的初始集合在直觉上是可计算的(因为它们非常简单)，而你能用来创建新原始递归函数的两个运算也是非常直接的。但是原始递归函数的集合不包含所有可能的可计算函数— 这可以看作康拖尔对角论证法的变体。这个论证提供了一个不是原始递归的可计算函数。证明的梗概如下:
原始递归函数集合可以被计算枚举。这个编号方案在函数定义上是唯一的，尽管在实际函数自身上不是唯一的(因为所有的函数都可以有无限数目的定义— 考虑简单的由恒等函数构成)。这个编码在可计算性的形式模型，比如递归函数或图灵机下定义的意义上是可计算的，邱奇-图灵论题涉及的任何机器都可以。
现在考虑一个矩阵，这里的行是在这个编号方案下的有一个参数的原始递归函数，而列是自然数。则每个元素(i, j) 对应于计算于数j 之上的第i 个一元原始递归函数。我们可以写为fᵢ(j)。
现在我们考虑函数g(x) = S(fₓ(x))。g 位于这个矩阵的对角线上，并简单的对它找到的值加一。这个函数是可计算的(按上述定义)，但是明显的没有计算它的原始递归函数存在，因为它与每个可能的原始递归函数都有至少一个值不同。所以，必然存在不是原始递归的可计算函数。
这个论证可以应用于能用这种方式枚举的任何一类的可计算(全)函数上。所以，任何这种可计算(全)函数的明确列表都不可能是完全的，比如那些可以用总是停机的机器计算的函数。但是要注意，偏可计算函数集合(那些不需要对所有参数有定义的函数)可以被明确的枚举，例如通过枚举图灵机编码。
可以明确展示的一个简单的1-元可计算函数阿克曼函数，它是对任何自然数递归定义的，但不是原始递归的。