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