程式扎記: [ 資料結構 小學堂 ] 堆疊 : 堆疊應用 (遞迴)

標籤

2010年9月23日 星期四

[ 資料結構 小學堂 ] 堆疊 : 堆疊應用 (遞迴)

前言 : 
堆疊在計算機領域的應用相當廣泛, 主要特性是它限制了資料的插入與刪除的位置與方法, 屬於有序串列應用. 至於它的應用可簡單列舉如下 : 

1. 二元數及森林的走訪運算, 例如中序追蹤, 前序追蹤等
2. 電腦中央處理器的中斷處理
3. 圖形的深度優先(DFS)追蹤法
4. 遞迴程式的呼叫與返回
5. 呼叫副程式以及返回處理, 例如要呼叫副程式前, 必須先將返回位置儲存到堆疊中, 然後才執行副程式, 等執行完畢再從堆疊取回返回位置.


遞迴 : 
遞迴 (Recursion) 在程式設計上是相當好用而且重要的概念. 使用遞迴可使程式變得簡潔, 但是設計時必須相當小心, 因為一不注意就會造成無窮迴圈或導致記憶體的浪費. 簡單的來說, 如果一個程式能被自己所定義或呼叫, 就稱為遞迴程式. 有些語言如 Fortran, Basic, COBOL 等並不具備遞迴功能. 原因是這些語言在編譯時就得決定所有相關資訊. 
至於像 C/C++ 等語言則可以使用遞迴功能, 因為他們的繫結時間可以延遲到執行時才動態決定. 只要程式語言具備遞迴功能, 任何能使用迴圈敘述 (for 或 while) 寫成的程式, 都能以遞迴成式取代. 例如 n! 的值就是一個很好的遞迴程式應用. 所謂 n! (n factorial) 就是 n 與 1 之間所有的正整數的乘積. 如 5!=5x4x3x2x1. 而 0! 定義為1. 

範例代碼 : 
在函式 ch04_04 使用迴圈計算 n! 的值, 而在 ch04_05 使用遞迴計算 n! 的值 : 
* ch04.h 代碼 : 

  1. /* 
  2. * 以 for 迴圈計算 0-i 階層值 
  3. */  
  4. int ch04_04(int i, bool b);  
  5.   
  6. /* 
  7. * 以遞回取代 for 迴圈計算 0-i 階層值 
  8. */  
  9. int ch04_05(int i, bool b);  
* ch04.cpp 代碼 : 

  1. int ch04_04(int i, bool b) {  
  2.     if(b) {  
  3.         if(i==1) {  
  4.             return 1;  
  5.         } else {  
  6.             int sum=1;  
  7.             for(int j=1; j<=i; j++) {  
  8.                 sum = sum * j;  
  9.             }  
  10.             return sum;  
  11.         }  
  12.     }  
  13.     return -1;  
  14. }  
  15.   
  16. int ch04_05(int i, bool b) {  
  17.     if(b) {  
  18.         if(i==1){  
  19.             return 1;  
  20.         } else {  
  21.             int sum = 1;  
  22.             sum = i * ch04_05(i-1,b);  
  23.             return sum;  
  24.         }  
  25.     }  
  26.     return -1;  
  27. }  
* 呼叫上述函式代碼 : 

  1.    cout << "計算4 階層的值: (使用 for 迴圈)" << endl;  
  2. int sum = ch04_04(4, b);  
  3. cout << "結果為=" << sum << endl;  
  4.    cout << "計算4 階層的值: (使用遞迴)" << endl;  
  5. sum = ch04_05(4, b);  
  6. cout << "結果為=" << sum << endl;  

執行結果 : 

計算4 階層的值: (使用 for 迴圈)
結果為=24
計算4 階層的值: (使用遞迴)
結果為=24

補充說明 : 
* [ 資料結構 小學堂 ] 堆疊 : 認識堆疊

沒有留言:

張貼留言

網誌存檔

關於我自己

我的相片
Where there is a will, there is a way!