摘要：遞歸函數的根本特征在于其逐步計算和分解計算，即通過某函數帶入到（返回，即“遞歸”）自身或另一個函數的變量來求解被帶入函數。這個定義是歷史上逐步定型化的，其定型的過程始終保持了其這一原始意義，但其函數的形式是逐步嚴格化的，其類型是逐步擴大的。當前，普遍地接受的“遞歸函數”即指哥德爾于1934年定義的“廣義遞歸函數（一般遞歸函數）”，包括 μ -遞歸函數、阿克曼遞歸函數以及在邏輯上可能出現的其他遞歸函數；廣義遞歸函數在外延上與下列概念具有邏輯等值意義：遞歸函數、能行可計算函數、 λ -可定義函數、圖靈可計算函數——這些函數都是廣義遞歸函數的不同側面的反映。