簡介PHP遞歸算法和應用

PHP作為開發動態頁面WEB的首選技術，對於它的基礎知識我們一定要牢記，這讓才能有助於編程。我們一起來看看PHP遞歸算法是怎麼回事吧。

1、調用子程序的含義：

當主程序執行到調用子程序A語句時，系統保存一些必要的現場數據，然後執行類似於BASIC語言的GOTO語句，跳轉到子程序A（為了說得簡單些，我這裡忽略了參數傳遞這個過程）。當子程序A執行到調用子程序B語句時，系統作法如上，跳轉到子程序B。子程序B執行完所有語句後，跳轉回子程序A調用子程序B語句的下一條語句（我這又忽略了返回值處理）子程序A執行完後，跳轉回主程序調用子程序A語句的下一條語句，主程序執行到結束。做個比較：我在吃飯（執行主程序）吃到一半時，某人叫我（執行子程序A），話正說到一半，電話又響了起來（執行子程序B），我只要先接完電話，再和某人把話說完，最後把飯吃完（我這飯吃得也夠累的了J）。

2、認識遞歸函數

我們在高中時都學過數學歸納法，PHP遞歸算法例如：

求 n！我們可以把n！這麼定義也就是說要求3！，我們必須先求出2！，要求2！，必須先求1！，要求1！，就必須先求0！，而0!=1，所以1!=0!*1=1，再進而求2!，3!。分別用函數表示，我們可以觀察到，除計算0！子程序外，其他的子程序基本相似，我們可以設計這麼一個子程序：

int factorial(int i){  
int res;  
res=factorial(I-1)*i;  
return res;  
} 

那麼當執行主程序語句s=factorial(3)時，就會執行factorial(3),但在執行factorial(3)，又會調用 factorial(2)，這時大家要注意，factorial(3)和factorial(2)雖然是同一個代碼段，但在內存中它的數據區是兩份！而執行factorial(2)時又會調用factorial（1），執行factorial（1）時又會調用factorial（0），每調用一次 factorial函數，它就會在內存中新增一個數據區，那麼這些復制了多份的函數大家可以把它看成是多個不同名的函數來理解；但我們這個函數有點問題，在執行factorial（0）時，它又會調用factorial（－1）。。。造成死循環，也就是說，在factorial函數中，我們要在適當的時候保證不再調用該函數，也就是不執行res=factorial(I-1)*i;這條調用語句。所以函數要改成：

int factorial(int i){  
int res;  
if (I>0) res=factorial(I-1)*i; else res=1;  
return res;  
} 

3、如何考慮用PHP遞歸算法來解決問題

例：求s=1+2+3+4+5+6+……+n本來這個問題我們過去常用循環累加的方法。而這裡如要用遞歸的方法，必須考慮兩點：
1） 能否把問題轉化成遞歸形式的描述；
2） 是否有遞歸結束的邊界條件。

顯然遞歸的兩個條件都有了：

1） s(n) =s(n-1)+n  
2） s(1)=1 

所以源程序為：

int progression(int n){  
int res;  
if (n=1 )res=1 else res=progression(n-1)+n;  
return res;  
} 

4、遞歸的應用

中序遍歷二叉樹

void inorder (BinTree T){  
if (T){  
inorder(T->lchild);  
printf(“%c”,T->data);  
inorder(T->rchild);  
}  
}