递归函数 在数理逻辑和计算机科学中递归函数或μ递归函数是一类从自然数到自然数的函数直觉上递归函数是可计算的事实上在可计算性理论中已经证明了它确实是图灵机的可计算函数递归函数与原始递归函数相关而且递归函数的归纳定义见下建立在原始递归函数之上但不是所有递归函数都是原始递归函数其中最著名的是阿克曼函数 其他等价的函数类是λ递归函数和马尔可夫算法可计算的函数 所有递归函数的集合叫做R