遞歸函數是什麼意思

遞歸函數是數論函數的一種，其定義域與值域都是自然數集，只是由於構作函數方法的不同而有別於其他的函數。

最簡單又最基本的函數有三個：零函數，射影函數，後繼函數，它們合稱初始函數。

要想由舊函數作出新函數，必須使用各種算子。在數理邏輯和計算機科學中，遞歸函數是一類從自然數到自然數的函數，它是在某種直覺意義上是"可計算的"。事實上，在可計算性理論中證明了遞歸函數精確的是圖靈機的可計算函數。