相对部分递归性(relative partial recursive -ness)部分可计算性概念的推广.若一个函式f可本原函式及集合A的特徵函式出发，经过有穷次叠置与一般递归得到，则称f相对部分递归于A，或称f为A部分递归的.形式地，可定义相对部分递归于A的函式类为满足以下4个条件的最小函式类A:
1.A包含本原函式.
2.A包含A的特徵函式.
3. A关于叠置封闭.
4.A关于一般递归式封闭.若函式f在A中，则称f相对部分递归于A.特别地，如果f又是全函式，则称f相对递归于A，或称为A递归的，如果集合B的特徵函式相对递归于A，则称B相对递归于A.
函式f相对部分递归于A，若且唯若f相对A计算;集合B相对递归于A，若且唯若B相对A可计算.所有A部分递归函式可能行枚举，并记为{君}eE},(参见“相对可计算性”).