數(shù)論函數(shù)的一種,其定義域與值域都是自然數(shù)集,只是由于構(gòu)作函數(shù)方法的不同而有別于其他的函數(shù)。處處有定義的函數(shù)叫做全函數(shù)，未必處處有定義的函數(shù)叫做部分函數(shù)。最簡(jiǎn)單又最基本的函數(shù)有三個(gè):零函數(shù)O(x)=0(其值恒為0);射影函數(shù)；后繼函數(shù)S(x)=x+1。它們合稱(chēng)初始函數(shù)。要想由舊函數(shù)作出新函數(shù)，必須使用各種算子。
代入（又名復(fù)合或疊置）是最簡(jiǎn)單又最重要的造新函數(shù)的算子，其一般形狀是：由一個(gè)m元函數(shù)?與m個(gè)n元函數(shù) g₁,g₂,…,g_m 造成新函數(shù) ? (g₁(x₁,x₂,…,x_n)，g₂(x₁,x₂,…,x_n),…,g_m(x₁,x₂，…，x_n)),亦可記為?(g₁，g₂,…,g_m)(x₁，x₂,…,x_n)。另一個(gè)造新函數(shù)的算子是原始遞歸式。具有n個(gè)參數(shù)u₁，u₂,…,u_n的原始遞歸式為：

具有一個(gè)參數(shù)的原始遞歸式可簡(jiǎn)寫(xiě)為：

其特點(diǎn)是，不能由g、h兩函數(shù)直接計(jì)算新函數(shù)的一般值?(u,x),而只能依次計(jì)算?(u,0)，?(u,1)，?(u,2)，…；但只要依次計(jì)算，必能把任何一個(gè)?(u,x)值都算出來(lái)。換句話說(shuō)只要g,h為全函數(shù)且可計(jì)算，則新函數(shù)f也是全函數(shù)且可計(jì)算。
由初始函數(shù)出發(fā)，經(jīng)過(guò)有限次的代入與原始遞歸式而作出的函數(shù)叫做原始遞歸函數(shù)。由于初始函數(shù)顯然是全函數(shù)且可計(jì)算，故原始遞歸函數(shù)都是全函數(shù)且可計(jì)算。通常使用的數(shù)論函數(shù)全是原始遞歸函數(shù)，可見(jiàn)原始遞歸函數(shù)是包括很廣的。但是W.阿克曼證明了，可以作出一個(gè)可計(jì)算的全函數(shù)，它不是原始遞歸的。經(jīng)過(guò)后人改進(jìn)后，這個(gè)函數(shù)可寫(xiě)為如下定義的阿克曼函數(shù)：

容易看出,這個(gè)函數(shù)是處處可計(jì)算的。任給m,n的值，如果m為0，可由第一式算出；如果m不為0而n為0，可由第二式化歸為求g(m,1)的值，這時(shí)第一變目減少了；如果m，n均不為0,根據(jù)第三式可先計(jì)算g(m,n-1),設(shè)為α，再計(jì)算g(m-1,α),前者第二變目減少（第一變目不變）,后者第一變目減少。極易用歸納法證得，這樣一步一步地化歸,最后必然化歸到第一變目為0，從而可用第一式計(jì)算。所以這個(gè)函數(shù)是處處可計(jì)算的。此外又容易證明，對(duì)任何一個(gè)一元原始遞歸函數(shù)?(x),永遠(yuǎn)可找出一數(shù)α使得?(x)<g(α,x)。這樣，g(x,x)+1便不是原始遞歸函數(shù)，否則將可找出一數(shù)b使得g(x,x)+1<g(b,x)。令x=b，即得g(b,b)+1<g(b,b)，而這是不可能的。
另一個(gè)重要的造新函數(shù)的算子是造逆函數(shù)的算子，例如，由加法而造減法，由乘法造除法等。一般，設(shè)已有函數(shù)?(u,x),就x解方程?(u,x)=t,可得x=g(u,t)。這時(shí)函數(shù)g叫做?的逆函數(shù)。至于解一般方程?(u，t,x)=0而得x＝g(u，t)可以看作求逆函數(shù)的推廣。解方程可以看作使用求根算子。?(u,t，x)=0的最小x根（如果有根的話），記為μx【?(u,t,x)=0】。當(dāng)方程沒(méi)有根時(shí),則認(rèn)為μx【?(u,t,x)=0】沒(méi)有定義?？梢?jiàn),即使?(u,t,x)處處有定義且可計(jì)算,但使用求根算子后所得的函數(shù)μx【?(u,t,x)=0】仍不是全函數(shù),可為部分函數(shù)。但只要它有定義，那就必然可以計(jì)算。這算子稱(chēng)為μ算子。如果?(u,t,x)本身便是部分函數(shù)，則 μx【?(u,t,x)=0】的意義是：當(dāng)?(u,t,n)可計(jì)算且其值為0,而x<n時(shí)?(u,t,x)均可計(jì)算而其值非0，則 μx【?(u,t,x)=0】指n；其他情況則作為無(wú)定義。例如，如果?(u,t,x)=0根本沒(méi)有根，或者雖然知道有一根為n，但?(u,t,n-1)不可計(jì)算,那么 μx【?(u,t,x)=0】都作為沒(méi)有定義。在這樣定義后,只要 μx【?(u,t,x)=0】有值便必可計(jì)算。由初始函數(shù)出發(fā),經(jīng)過(guò)有窮次使用代入、原始遞歸式與 μ算子而作成的函數(shù)叫做部分遞歸函數(shù)，處處有定義的部分遞歸函數(shù)稱(chēng)為全遞歸函數(shù)，或一般遞歸函數(shù)。
原始遞歸函數(shù)類(lèi)里還有一個(gè)重要的子類(lèi)稱(chēng)為初等函數(shù)類(lèi),它是由非負(fù)整數(shù)與變?cè)?jīng)過(guò)有窮次加、算術(shù)減（即｜α-b｜）、乘、算術(shù)除、疊加Σ、疊乘П而得的函數(shù)組成的類(lèi)。
波蘭人A.格熱高契克把原始遞歸函數(shù)類(lèi)按定義的復(fù)雜程度來(lái)分類(lèi)，稱(chēng)為格熱高契克分層或波蘭分層。
要把遞歸函數(shù)應(yīng)用于謂詞，首先要定義謂詞的特征函數(shù)。謂詞R(x,y)的特征函數(shù)是

稱(chēng)謂詞R 是遞歸謂詞，若R 的特征函數(shù)是遞歸函數(shù)；稱(chēng)自然數(shù)子集A為遞歸集,若謂詞x∈A是遞歸謂詞。有了上述定義，就可以用遞歸函數(shù)來(lái)處理遞歸謂詞和遞歸集。為了處理N×N（其中N 為自然數(shù)集）的子集，就要建立配對(duì)函數(shù),所謂配對(duì)函數(shù)通常是指由N×N 到N 的一個(gè)函數(shù)?(x，y)與它的逆函數(shù)g₁(z)，g₂(z)。它們都滿(mǎn)足以下關(guān)系。

一個(gè)函數(shù)在它的函數(shù)體內(nèi)調(diào)用它自身稱(chēng)為遞歸調(diào)用。這種函數(shù)稱(chēng)為遞歸函數(shù)。這對(duì)于程序員來(lái)說(shuō)，通常有很高的實(shí)用價(jià)值，常用來(lái)將復(fù)雜的問(wèn)題分解為簡(jiǎn)單的并相同的情況，反復(fù)做這種處理直到問(wèn)題解決。

用遞歸函數(shù)與不用遞歸函數(shù)的區(qū)別

示例一：使用靜態(tài)變量

示例二：使用遞歸函數(shù)和循環(huán)實(shí)現(xiàn)字符串逆轉(zhuǎn)排列

遞歸函數(shù)很多時(shí)候我們可以循環(huán)替代，建議當(dāng)我們不能用循環(huán)替代時(shí)再用，因?yàn)橛醚h(huán)我們更容易理解，更不容易出錯(cuò)。

php遞歸函數(shù) php支付遞歸函數(shù)，遞歸函數(shù)就是調(diào)用自己本身，這些函數(shù)特別適用于瀏覽動(dòng)態(tài)數(shù)據(jù)結(jié)構(gòu)，例如樹(shù)和列表。
幾乎沒(méi)有web應(yīng)用程序要求使用復(fù)雜的數(shù)據(jù)結(jié)構(gòu)

這個(gè)程序清單中實(shí)現(xiàn)兩個(gè)函數(shù)，這兩個(gè)函數(shù)都可以相反的順序打印字符串的內(nèi)容

函數(shù)reversr_r是通過(guò)遞歸實(shí)現(xiàn)的，而函數(shù)reverse_i()是通過(guò)循環(huán)實(shí)現(xiàn)的

遞歸函數(shù)即自調(diào)用函數(shù)，在函數(shù)體內(nèi)部直接或者間接的自己調(diào)用自己，即函數(shù)的嵌套調(diào)用是函數(shù)本身。通常在此類(lèi)型的函數(shù)提之中會(huì)附加一個(gè)條件判斷敘述，以判斷是否需要執(zhí)行遞歸調(diào)用，并且在特定的條件下終止函數(shù)的遞歸調(diào)用動(dòng)作，把目前流程的主控權(quán)交回到上一層函數(shù)來(lái)執(zhí)行。以此，當(dāng)某個(gè)執(zhí)行遞歸調(diào)用的函數(shù)沒(méi)有附加條件判斷敘述時(shí)，可能會(huì)造成無(wú)限循環(huán)的錯(cuò)誤情形。

函數(shù)遞歸調(diào)用最大的好處在于可以精簡(jiǎn)程序中的復(fù)雜重復(fù)調(diào)用程序，并且能以這種特性來(lái)執(zhí)行一些較為復(fù)雜的運(yùn)算動(dòng)作。例如，列表、動(dòng)態(tài)樹(shù)形菜單及遍歷目錄等操作。相應(yīng)的非遞歸函數(shù)雖然效率高，但卻比較難編程，而且相對(duì)來(lái)說(shuō)可讀性差。現(xiàn)代程序設(shè)計(jì)的目標(biāo)主要是可讀性好。隨著計(jì)算機(jī)硬件性能的不斷提高，程序在更多的場(chǎng)合優(yōu)先考慮可讀而不是高效，所以，鼓勵(lì)用遞歸函數(shù)實(shí)現(xiàn)程序思想。

一個(gè)簡(jiǎn)單的遞歸調(diào)用實(shí)例如下所示：

該程序執(zhí)行后輸出如下的結(jié)果：

找到結(jié)果中后半部分的數(shù)字正向順序輸出的原因

說(shuō)明：在上面的實(shí)例中聲明了一個(gè) test()函數(shù)，該函數(shù)需要一個(gè)整型的參數(shù)。在函數(shù)外面通過(guò)傳遞整數(shù) 10 作為參數(shù)調(diào)用 test()函數(shù)。在 test()函數(shù)體中，第一條代碼輸出參數(shù)的值和一個(gè)空格。然后判斷條件是否成立，成立則調(diào)用自己并將參數(shù)減 1 再次傳入。開(kāi)始調(diào)用時(shí)，它是外層調(diào)內(nèi)層，內(nèi)層調(diào)更內(nèi)一層，直到最內(nèi)層由于條件不允許必須結(jié)束。最內(nèi)存結(jié)束了，輸出 <--------> 作為分界符，執(zhí)行調(diào)用之后的代碼輸出參數(shù)的值和空格，它就會(huì)回到稍外一層繼續(xù)執(zhí)行。稍外一層在結(jié)束時(shí)，退回到在稍外一層繼續(xù)執(zhí)行，層層推出，直到最外層結(jié)束。執(zhí)行完成以后的結(jié)果就是我們上面看到的結(jié)果。

樹(shù)型菜單在很多桌面應(yīng)用系統(tǒng)中都有非常廣泛的應(yīng)用，其主要優(yōu)點(diǎn)是結(jié)構(gòu)清晰，利于使用者非常清楚的知道目前自己所在的位置。但在web上樹(shù)型菜單的應(yīng)用因?yàn)闆](méi)有理想的現(xiàn)成組件可以拿過(guò)來(lái)直接使用，所以一般的情況下，程序員主要是通過(guò)JavaScript來(lái)實(shí)現(xiàn)一些簡(jiǎn)單的樹(shù)型結(jié)構(gòu)菜單，但這些菜單往往都是事先定好各菜單項(xiàng)目，以及各菜單項(xiàng)目之間的層次關(guān)系，不利于擴(kuò)充，一旦需要另一個(gè)菜單結(jié)構(gòu)時(shí)，往往還需要重新編寫(xiě)，因此使用起來(lái)不是很方便。

??? 經(jīng)過(guò)對(duì)函數(shù)遞歸的研究，我發(fā)現(xiàn)這種樹(shù)型菜單可以通過(guò)遞歸函數(shù)，使樹(shù)型菜單的顯示實(shí)現(xiàn)動(dòng)態(tài)變化，并沒(méi)有級(jí)數(shù)的限制。下面就是我用php,MySQL,JavaScript寫(xiě)的一個(gè)動(dòng)態(tài)樹(shù)型菜單的處理代碼，如果大家有興趣的話，就和我一起來(lái)看看我是如何實(shí)現(xiàn)的吧：）

??? 首先，我們需要一個(gè)數(shù)據(jù)庫(kù)，在這個(gè)數(shù)據(jù)庫(kù)中，我們建立以下一張表：

CREATE TABLE menu (
id tinyint(4) NOT NULL auto_increment,
parent_id tinyint(4) DEFAULT \\'0\\' NOT NULL,
name varchar(20),
url varchar(60),
PRIMARY KEY (id)
);

??? 這張表中
??? id 為索引
??? parent_id 用來(lái)保存上一級(jí)菜單的id號(hào)，如果是一級(jí)菜單則為0
??? name 為菜單的名稱(chēng)，也就是要在頁(yè)面上顯示的菜單內(nèi)容
??? url 如果某菜單為末級(jí)菜單，則需要指定該連接的url地址，這個(gè)字段就是用來(lái)保存此地址的，其他非末級(jí)菜單，該字段為空