發信人: ax.bbs@bbs.ee.nthu.edu.tw. (athena), 信區: test
標  題: 星星流講座 0041
發信站: ☆清華電機☆ (Sat Jul  8 17:37:54 1995)
轉信站: star

星星流講座 0041         C 語言教室

第 6 講 之 4            函數
                        Topic: Recursion (1)

我們前面提到過，呼叫一個函數，就是把程式的控制權交給函數，
當函數執行完之後，再把控制權交回來。例如：

void main (void)                        ↓ main() 開始執行
{                                       ↓
    /* main() start here */             ↓
    foo ();                              ─┐ 把控制權交給 foo()
    /* main() continue here */       ┌→  │
}                                    │    │
                                     │  ─┘
void foo (void)                      │ ↓ foo() 開始執行
{                                    │ ↓
    /* foo() work here */            │ ↓
}                                    └─ 執行完畢，把控制權還給 main()

那如果我們在函數之中呼叫函數本身呢？例如：

void foo (void)
{
    foo ();
}

這時候控制權的流向就會如下：

        (第一個) foo()
                  ↓ 呼叫 foo()，把控制權交給 foo()
        (第二個) foo()
                  ↓ 呼叫 foo()，把控制權交給 foo()
        (第三個) foo()
                  ↓ 呼叫 foo()，把控制權交給 foo()
                  ：
                  ：

控制權交出去之後就不會回來了，這是一種很危險的動作，其實這就是一種
錯誤的遞迴 (recursion)。什麼叫做遞迴呢？遞迴就是函數直接或間接地叫
用自己。什麼時候我們會用的上遞迴函數呢？一個常見的例子是求某數的階
乘：

int factor (int n)
{
    if (n < 0)
        return factor (n + 1) * n;
    else if (n > 0)
        return factor (n - 1) * n;
    else                                /* n == 0 */
        return 1;                       /* 0! = 1 */
}

我們知道

        n * (n - 1)! if n > 0
   n! = n * (n + 1)! if n < 0
        1            if n = 0

直覺地寫成程式就變成了上面 factor() 這個函數 (當然，這個函數在實
際上並不實用，實用的階乘函數並不容易作出來)，這是一個標準的遞迴
的寫法。遞迴函數有三大要件：起始條件、遞迴終止條件、遞迴本體。
在我們上面的例子中，起始條件就是參數 n (要求 n 的階乘)，而遞迴
終止條件則是 n == 0 (當 n = 0 時傳回 1，不再繼續遞迴)，遞迴的本
體是 factor (n + 1) * n 及 factor (n - 1) * n 這兩個實際呼叫遞迴
函數的部份。

我們現在花點時間來 trace 一下 factor (3) 的動作：

        呼叫 factor (3)
             │
             │
             ↓
       return factor (2) * 3    傳回 2*3=6，函數結束
             │          ↖─────────┐
        呼叫 factor(2)                       │
             ↓                              │
       return factor (1) * 2       傳回 1*2=2 給 factor(3)    
             │          ↖────────┐
        呼叫 factor(1)                     │
             ↓                            │
       return factor (0) * 1      傳回 1*1=1 給 factor(2)
             │          ↖─┐
        呼叫 factor(0)       │
             ↓              │
          return 1 ─────┘ 傳回 1 給 factor(1) 

為什麼我們說終止條件是 n == 0 呢？因為它是遞迴函數不再繼續呼叫
自己的判斷條件，所以叫做遞迴終止條件。每一個遞迴函數都必須設定
遞迴終止條件，至於遞迴終止條件要如何找出來呢？它通常是數學中所
謂的邊界條件 (boundry condition)，只要多多練習大概就能一眼就看
出來了。
--
本文原作者為徐振家，原作刊載於星星神教總壇 ☆清華電機☆ test 板。
你可以以電子文件的形式將本文自由流傳於台灣學術網路，但必須包含此版權聲明。
原作者依中華民國著作權法之規定，享有本文之著作權，請勿抄襲以免觸法。
未經授權任何人不得以任何形式對本文做任何修改及商業上之應用。
其他網路的轉載或其他用途的應用，請先知會作者，並取得其同意。
對本文有任何疑問或意見請 mail 給 ax.bbs@bbs.ee.nthu.edu.tw，謝謝。