次遞歸函式

次遞歸函式(subrecursive function)一類可計算函式.其特點是這種函式的計算複雜性可預先估計.例如，斐波那契函式f(f(o>=.fW一l,f}x-I- 2 ) =.f (x ) -I-f (x-I-1) )在x(,2)處的值可用二一1次加法運算而得，因此稱f為次遞歸函式.此外，原始遞歸函式、初等函式、多項式時間可計算函式等都是次遞歸函式.由於次遞歸函式要比一般的遞歸函式具有較低的計算複雜性，有著十分重要的套用價值和理論意義，因此，對次遞歸函式的研究已成為遞歸論中的非常活躍的研究分支.