數(shù)論函數(shù)的一種,其定義域與值域都是自然數(shù)集,只是由于構(gòu)作函數(shù)方法的不同而有別于其他的函數(shù)。處處有定義的函數(shù)叫做全函數(shù)，未必處處有定義的函數(shù)叫做部分函數(shù)。最簡單又最基本的函數(shù)有三個:零函數(shù)O(x)=0(其值恒為0);射影函數(shù)
；后繼函數(shù)S(x)=x+1。它們合稱初始函數(shù)。要想由舊函數(shù)作出新函數(shù)，必須使用各種算子。
代入（又名復(fù)合或疊置）是最簡單又最重要的造新函數(shù)的算子，其一般形狀是：由一個m元函數(shù)?與m個n元函數(shù) g1,g2,…,gm 造成新函數(shù) ? (g1(x1,x2,…,xn)，g2(x1,x2,…,xn),…,gm(x1,x2，…，xn)),亦可記為?(g1，g2,…,gm)(x1，x2,…,xn)。另一個造新函數(shù)的算子是原始遞歸式。具有n個參數(shù)u1，u2,…,un的原始遞歸式為：
具有一個參數(shù)的原始遞歸式可簡寫為：
其特點是，不能由g、h兩函數(shù)直接計算新函數(shù)的一般值?(u,x),而只能依次計算?(u,0)，?(u,1)，?(u,2)，…；但只要依次計算，必能把任何一個?(u,x)值都算出來。換句話說只要g,h為全函數(shù)且可計算，則新函數(shù)f也是全函數(shù)且可計算。
由初始函數(shù)出發(fā)，經(jīng)過有限次的代入與原始遞歸式而作出的函數(shù)叫做原始遞歸函數(shù)。由于初始函數(shù)顯然是全函數(shù)且可計算，故原始遞歸函數(shù)都是全函數(shù)且可計算。通常使用的數(shù)論函數(shù)全是原始遞歸函數(shù)，可見原始遞歸函數(shù)是包括很廣的。但是W.阿克曼證明了，可以作出一個可計算的全函數(shù)，它不是原始遞歸的。經(jīng)過后人改進后，這個函數(shù)可寫為如下定義的阿克曼函數(shù)：
容易看出,這個函數(shù)是處處可計算的。任給m,n的值，如果m為0，可由第一式算出；如果m不為0而n為0，可由第二式化歸為求g(m,1)的值，這時第一變目減少了；如果m，n均不為0,根據(jù)第三式可先計算g(m,n-1),設(shè)為α，再計算g(m-1,α),前者第二變目減少（第一變目不變）,后者第一變目減少。極易用歸納法證得，這樣一步一步地化歸,最后必然化歸到第一變目為0，從而可用第一式計算。所以這個函數(shù)是處處可計算的。此外又容易證明，對任何一個一元原始遞歸函數(shù)?(x),永遠可找出一數(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)，而這是不可能的。
另一個重要的造新函數(shù)的算子是造逆函數(shù)的算子，例如，由加法而造減法，由乘法造除法等。一般，設(shè)已有函數(shù)?(u,x),就x解方程?(u,x)=t,可得x=g(u,t)。這時函數(shù)g叫做?的逆函數(shù)。至于解一般方程?(u，t,x)=0而得x＝g(u，t)可以看作求逆函數(shù)的推廣。解方程可以看作使用求根算子。?(u,t，x)=0的最小x根（如果有根的話），記為μx【?(u,t,x)=0】。當(dāng)方程沒有根時,則認(rèn)為μx【?(u,t,x)=0】沒有定義。可見,即使?(u,t,x)處處有定義且可計算,但使用求根算子后所得的函數(shù)μx【?(u,t,x)=0】仍不是全函數(shù),可為部分函數(shù)。但只要它有定義，那就必然可以計算。這算子稱為μ算子。如果?(u,t,x)本身便是部分函數(shù)，則 μx【?(u,t,x)=0】的意義是：當(dāng)?(u,t,n)可計算且其值為0,而x<n時?(u,t,x)均可計算而其值非0，則 μx【?(u,t,x)=0】指n；其他情況則作為無定義。例如，如果?(u,t,x)=0根本沒有根，或者雖然知道有一根為n，但?(u,t,n-1)不可計算,那么 μx【?(u,t,x)=0】都作為沒有定義。在這樣定義后,只要 μx【?(u,t,x)=0】有值便必可計算。由初始函數(shù)出發(fā),經(jīng)過有窮次使用代入、原始遞歸式與 μ算子而作成的函數(shù)叫做部分遞歸函數(shù)，處處有定義的部分遞歸函數(shù)稱為全遞歸函數(shù)，或一般遞歸函數(shù)。
原始遞歸函數(shù)類里還有一個重要的子類稱為初等函數(shù)類,它是由非負整數(shù)與變元經(jīng)過有窮次加、算術(shù)減（即｜α-b｜）、乘、算術(shù)除
、疊加Σ、疊乘П而得的函數(shù)組成的類。
波蘭人A.格熱高契克把原始遞歸函數(shù)類按定義的復(fù)雜程度來分類，稱為格熱高契克分層或波蘭分層。
要把遞歸函數(shù)應(yīng)用于謂詞，首先要定義謂詞的特征函數(shù)。謂詞R(x,y)的特征函數(shù)是
稱謂詞R 是遞歸謂詞，若R 的特征函數(shù)是遞歸函數(shù)；稱自然數(shù)子集A為遞歸集,若謂詞x∈A是遞歸謂詞。有了上述定義，就可以用遞歸函數(shù)來處理遞歸謂詞和遞歸集。為了處理N×N（其中N 為自然數(shù)集）的子集，就要建立配對函數(shù),所謂配對函數(shù)通常是指由N×N 到N 的一個函數(shù)?(x，y)與它的逆函數(shù)g1(z)，g2(z)。它們都滿足以下關(guān)系。
一個函數(shù)在它的函數(shù)體內(nèi)調(diào)用它自身稱為遞歸調(diào)用。這種函數(shù)稱為遞歸函數(shù)。這對于程序員來說，通常有很高的實用價值，常用來將復(fù)雜的問題分解為簡單的并相同的情況，反復(fù)做這種處理直到問題解決。
用遞歸函數(shù)與不用遞歸函數(shù)的區(qū)別
示例一：使用靜態(tài)變量
|
1
2
3
4
5
6
7
8
|
function test(){??static $dig=0;??if($dig++<10){????echo $dig;????test();??}}test();//12345678910 |
示例二：使用遞歸函數(shù)和循環(huán)實現(xiàn)字符串逆轉(zhuǎn)排列
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
|
function unreverse($str){??for($i=1;$i<=strlen($str);$i++){????echo substr($str,-$i,1);??}}unreverse("abcdefg");//gfedcbcfunction reverse($str){??if(strlen($str)>0){????reverse(substr($str,1));????echo substr($str,0,1);????return;??}}reverse("abcdefg");//gfedcbc |
遞歸函數(shù)很多時候我們可以循環(huán)替代，建議當(dāng)我們不能用循環(huán)替代時再用，因為用循環(huán)我們更容易理解，更不容易出錯。
php遞歸函數(shù) php支付遞歸函數(shù)，遞歸函數(shù)就是調(diào)用自己本身，這些函數(shù)特別適用于瀏覽動態(tài)數(shù)據(jù)結(jié)構(gòu)，例如樹和列表。
幾乎沒有web應(yīng)用程序要求使用復(fù)雜的數(shù)據(jù)結(jié)構(gòu)
|
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
|
<?phpfunction reversr_r($str){if (strlen($str)>0)reverse_r(substr($str,1));echo substr($str,0,1);return;}?><?phpfunction reverse_i($str){for($i=1;$i<=strlen($str);$i++){echo substr($str,-$i,1);}} |
這個程序清單中實現(xiàn)兩個函數(shù)，這兩個函數(shù)都可以相反的順序打印字符串的內(nèi)容
函數(shù)reversr_r是通過遞歸實現(xiàn)的，而函數(shù)reverse_i()是通過循環(huán)實現(xiàn)的
遞歸函數(shù)即自調(diào)用函數(shù)，在函數(shù)體內(nèi)部直接或者間接的自己調(diào)用自己，即函數(shù)的嵌套調(diào)用是函數(shù)本身。通常在此類型的函數(shù)提之中會附加一個條件判斷敘述，以判斷是否需要執(zhí)行遞歸調(diào)用，并且在特定的條件下終止函數(shù)的遞歸調(diào)用動作，把目前流程的主控權(quán)交回到上一層函數(shù)來執(zhí)行。以此，當(dāng)某個執(zhí)行遞歸調(diào)用的函數(shù)沒有附加條件判斷敘述時，可能會造成無限循環(huán)的錯誤情形。
函數(shù)遞歸調(diào)用最大的好處在于可以精簡程序中的復(fù)雜重復(fù)調(diào)用程序，并且能以這種特性來執(zhí)行一些較為復(fù)雜的運算動作。例如，列表、動態(tài)樹形菜單及遍歷目錄等操作。相應(yīng)的非遞歸函數(shù)雖然效率高，但卻比較難編程，而且相對來說可讀性差。現(xiàn)代程序設(shè)計的目標(biāo)主要是可讀性好。隨著計算機硬件性能的不斷提高，程序在更多的場合優(yōu)先考慮可讀而不是高效，所以，鼓勵用遞歸函數(shù)實現(xiàn)程序思想。
一個簡單的遞歸調(diào)用實例如下所示：
|
1
2
3
4
5
6
7
8
9
10
11
12
13
|
<?php?//聲明一個函數(shù)，用于測試遞歸?function test($n){???echo $n." ";??????? //在函數(shù)開始輸出參數(shù)的值???if($n>0){??????????????? //判斷參數(shù)是否大于0?????test($n-1);??????????? //如果參數(shù)大于0則調(diào)用自己，并將參數(shù)減1后再次傳入???}else{?????????????????? //判斷參數(shù)是不大于0?????echo "<-------->? ";???}???echo $n." ";?}?test(10);?????????????????? //調(diào)用test函數(shù)將整數(shù)10傳給參數(shù)?> |
該程序執(zhí)行后輸出如下的結(jié)果：
|
1
|
10 9 8 7 6 5 4 3 2 1 0 <--------> 0 1 2 3 4 5 6 7 8 9 10 |
找到結(jié)果中后半部分的數(shù)字正向順序輸出的原因
說明：在上面的實例中聲明了一個 test()函數(shù)，該函數(shù)需要一個整型的參數(shù)。在函數(shù)外面通過傳遞整數(shù) 10 作為參數(shù)調(diào)用 test()函數(shù)。在 test()函數(shù)體中，第一條代碼輸出參數(shù)的值和一個空格。然后判斷條件是否成立，成立則調(diào)用自己并將參數(shù)減 1 再次傳入。開始調(diào)用時，它是外層調(diào)內(nèi)層，內(nèi)層調(diào)更內(nèi)一層，直到最內(nèi)層由于條件不允許必須結(jié)束。最內(nèi)存結(jié)束了，輸出 <--------> 作為分界符，執(zhí)行調(diào)用之后的代碼輸出參數(shù)的值和空格，它就會回到稍外一層繼續(xù)執(zhí)行。稍外一層在結(jié)束時，退回到在稍外一層繼續(xù)執(zhí)行，層層推出，直到最外層結(jié)束。執(zhí)行完成以后的結(jié)果就是我們上面看到的結(jié)果。
樹型菜單在很多桌面應(yīng)用系統(tǒng)中都有非常廣泛的應(yīng)用，其主要優(yōu)點是結(jié)構(gòu)清晰，利于使用者非常清楚的知道目前自己所在的位置。但在web上樹型菜單的應(yīng)用因為沒有理想的現(xiàn)成組件可以拿過來直接使用，所以一般的情況下，程序員主要是通過JavaScript來實現(xiàn)一些簡單的樹型結(jié)構(gòu)菜單，但這些菜單往往都是事先定好各菜單項目，以及各菜單項目之間的層次關(guān)系，不利于擴充，一旦需要另一個菜單結(jié)構(gòu)時，往往還需要重新編寫，因此使用起來不是很方便。
??? 經(jīng)過對函數(shù)遞歸的研究，我發(fā)現(xiàn)這種樹型菜單可以通過遞歸函數(shù)，使樹型菜單的顯示實現(xiàn)動態(tài)變化，并沒有級數(shù)的限制。下面就是我用php,MySQL,JavaScript寫的一個動態(tài)樹型菜單的處理代碼，如果大家有興趣的話，就和我一起來看看我是如何實現(xiàn)的吧：）
??? 首先，我們需要一個數(shù)據(jù)庫，在這個數(shù)據(jù)庫中，我們建立以下一張表：
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 用來保存上一級菜單的id號，如果是一級菜單則為0
??? name 為菜單的名稱，也就是要在頁面上顯示的菜單內(nèi)容
??? url 如果某菜單為末級菜單，則需要指定該連接的url地址，這個字段就是用來保存此地址的，其他非末級菜單，該字段為空