遞歸函數

定義

一種計算過程，如果其中每一步都要用到前一步或前幾步的結果，稱為遞歸的。用遞歸過程定義的函數，稱為遞歸函數，例如連加、連乘及階乘等。凡是遞歸的函數，都是可計算的，即能行的。

古典遞歸函數，是一種定義在自然數集合上的函數，它的未知值往往要通過有限次運算回歸到已知值來求出，故稱為“遞歸”。它是古典遞歸函數論的研究對象。

介紹

在數理邏輯和計算機科學中，遞歸函數或μ-遞歸函數是一類從自然數到自然數的函數，它是在某種直覺意義上是"可計算的"。事實上，在可計算性理論中證明了遞歸函數精确的是圖靈機的可計算函數。

遞歸函數有關于原始遞歸函數，并且它們的歸納定義(見下)建造在原始遞歸函數之上。但是，不是所有遞歸函數都是原始遞歸函數—最著名的這種函數是阿克曼函數。