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