次遞歸函式

次遞歸函式(subrecursive function)一類可計算函式。

基本介紹

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

相關詞條

熱門詞條

聯絡我們