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

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

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 代碼 : 

view plaincopy to clipboardprint?

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 代碼 : 

view plaincopy to clipboardprint?

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. }  

* 呼叫上述函式代碼 : 

view plaincopy to clipboardprint?

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

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