遞迴

嚴格來說，遞迴 (recursion) 並不是流程控制結構， 它只是讓一個函式呼叫它自己而已。 但是，因為在思考方法上，遞迴可以和迭代做對比， 所以我們還是認為遞迴是流程控制方法的一種。

以下是一個很單純的計算階乘 (factorial) 的程式。 我們知道，若 n 是正整數，n! 的定義就是 n * (n-1)!，而 0! 定義成 1。 所以，利用遞迴的想法來寫一個 fac() 函式，再寫個簡單的主程式來呼叫它， 就是以下的範例。

#include <stdio.h>
 
main() {
    int i, fac(int);
    for (i=0; i<6; ++i)
        printf("%d! = %d\n", i, fac(i));
}
  
int fac(int n) {
    if (n > 0)
        return n * fac(n-1);
    if (n <= 0)
        return 1;
}

    int i, fac(int);

    int i;
    int fac(int);

我們明白，完全沒必要使用用遞迴來計算階乘。用 for 或 while 迴圈都辦得到。此處只是一個例子。 而且，從這個例子裡面，我們似乎可以看出來， 應該是所有的遞迴，都可以用迭代來取代。 而且，事實上迭代結構的程式執行效率，通常必定遠高於遞迴： 不論在空間效率上、還是時間效率上，遞迴都略遜至少一籌。

那麼，我們何苦要使用遞迴結構呢？ 因為，在許多情況下，遞迴是一種最自然的想法。 利用遞迴想法所寫出來的函式，可以非常短。 而且，只要學會這種思考方式，遞迴的程式也很好理解。 在這些情況下，固然可以將程式改以迭代結構來設計， 但是更改後的版本，可能很難寫，或者很難想清楚。 在機器效能日益提高的情況下，我們寧願犧牲機器的執行效率， 換取我們寫程式的效率。

習題

[ 前一節 ]‧[ 後一節 ]‧[ 回目錄 ]

注意：此處所有文件均為原著，個別的版權宣告日後會一一公布， 整體版面設計亦尚未完成。但仍請勿抄襲文字與圖片，以免觸犯著作權法。

Created: May 21, 2000
Last Revised: Feb 25, 2001
© Copyright 2001 Wei-Chang Shann 單維彰

• Back to the home page of Wei-Chang Shann.
• Connect to the home page of Department of Mathematics, National Central University, Taiwan.