遞歸是計(jì)算機(jī)應(yīng)用里的一門學(xué)問。遞歸函數(shù)，學(xué)過數(shù)學(xué)的都知道遞歸是數(shù)學(xué)里的一大難點(diǎn)，而到了計(jì)算機(jī)里更是難以接受。

在編程語言中，函數(shù)直接或間接調(diào)用函數(shù)本身，則該函數(shù)稱為遞歸函數(shù)。遞歸函數(shù)不能定義為內(nèi)聯(lián)函數(shù)。

在數(shù)學(xué)上，關(guān)于遞歸函數(shù)的定義如下對于某一函數(shù)fx，其定義域是集合a，那么若對于a集合中的某一個(gè)值x0，其函數(shù)值fx0由ffx0決定，那么就稱fx為遞歸函數(shù)。中文名遞歸函數(shù)。

連乘及階乘等。凡是遞歸的函數(shù)，都是可計(jì)算的，即能行的[1]。

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

在數(shù)理邏輯和計(jì)算機(jī)科學(xué)中，遞歸函數(shù)或μ遞歸函數(shù)是一類從自然數(shù)到自然數(shù)的函數(shù)，它是在某種直覺意義上是“可計(jì)算的“。事實(shí)上，在可計(jì)算性理論中證明了遞歸函數(shù)精確的是圖靈機(jī)的可計(jì)算函數(shù)。遞歸函數(shù)有關(guān)于原始遞歸函數(shù)，并且它們的歸納定義見下建造在原始遞歸函數(shù)之上。但是，不是所有遞歸函數(shù)都是原始遞歸函數(shù)—最著名的這種函數(shù)是阿克曼函數(shù)。

其他等價(jià)的函數(shù)類是λ遞歸函數(shù)和馬爾可夫算法可計(jì)算的函數(shù)。

是所謂能行可計(jì)算函數(shù)，另一類是非能行可計(jì)算的函數(shù)。這前一種函數(shù)無論在理論上或在實(shí)際上都是非常重要的，因此人們便試圖給它們以精確的數(shù)學(xué)刻畫。遞歸函數(shù)便是許多這種刻畫中的一種?。

我們所考慮的關(guān)于遞歸函數(shù)的例子函數(shù)都是從自然數(shù)到自然數(shù)的函數(shù)。這樣便于理解和認(rèn)知。遞歸算法一般用于解決三類問題

首先，數(shù)據(jù)的定義是按遞歸定義的。

其次，問題解法按遞歸算法實(shí)現(xiàn)。

在這類問題雖則本身沒有明顯的遞歸結(jié)構(gòu)，但用遞歸求解比迭代求解更簡單，如hanoi問題。

最后數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的。

比如如二叉樹、廣義表等，由于結(jié)構(gòu)本身固有的遞歸特性，則它們的操作可遞歸地描述。

當(dāng)然，對遞歸的應(yīng)用也存在不可避免的缺點(diǎn)

遞歸算法解題相對常用的算法如普通循環(huán)等，運(yùn)行效率較低。因此，應(yīng)該盡量避免使用遞歸，除非沒有更好的算法或者某種特定情況，遞歸更為適合的時(shí)候。在遞歸調(diào)用的過程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開辟了棧來存儲。遞歸次數(shù)過多容易造成棧溢出等。

遞歸典型問題梵塔問題（漢諾塔問題）

遞歸函數(shù)的學(xué)問說大不大，說小也不小。內(nèi)行人看門道，外行人看熱鬧，想要真正的了解和掌握，還要更深入的學(xué)習(xí)和認(rèn)知。