發信人: ax.bbs@bbs.ee.nthu.edu.tw.
(athena), 信區: test
標 題: 星星流講座 0042
發信站: ☆清華電機☆ (Tue Jul 18 22:54:26 1995)
轉信站: star
星星流講座 0042 C 語言教室
第 6 講 之 5 函數
Topic: Recursion (2)
前頭我們講了什麼叫做遞迴，我們現在來研究一下遞迴的優缺點：
遞迴的優點：某些問題是以遞迴的方式定義的，以遞迴函數來製作
會比較簡潔易懂，程式寫作的時間也可以縮短。
遞迴的缺點：遞迴函數花費了太多的能量，執行起來通常較非遞迴
的版本為慢。
在此我們解釋一下「能量」的意義：以硬體的觀念來講，函數是放
在記憶體中的一群指令，而每個函數被放置在不同的記憶體，如下
圖所示：
┌──────────────────────────────┐
│ ┌─────────────────────────┐ │
│ │IP↘ code (text) │ │
│ │ ┌───┐ ┌────┐ ┌────┐ │ │
│ │ │main()│ │函數 A()│ │函數 B()│ │ │
│ │ └───┘ └────┘ └────┘ │ │
│ └─────────────────────────┘ │
│ ┌────────┐┌───┐┌─────────┐ │
│ │ data heap ││stack ││global name space │ │
│ └────────┘└───┘└─────────┘ │
└──────────────────────────────┘
所有的程式碼都被放置在 code 這塊記憶體裡，也只有程式碼才可以放在
code 中，我們也常把 code 這塊記憶體叫做 text，意即程式的本文之意
。所有的區域變數都被放在 data heap 這塊記憶體中。stack 這
塊記憶體是給編譯程式和作業系統應用的，我們通常無法直接取用。所有
的靜態變數、全域變數以及外部變數都被放在 global name space 中，
在 UNIX 系統下這塊記憶體也叫做 bss。一個程式要佔據多大的記憶體，
在 UNIX 系統下可以用 size 這個指令看出來，例如我們想看看 gcc 佔了
多大的記憶體空間：
[thccy14]/usr/local/bin> size gcc
text data bss dec hex filename
57312 8192 0 65504 ffe0 gcc
可以看到 gcc 的 code 有 57312 bytes 大，需要 8192 bytes 的 data
heap，不需要 bss。
那麼程式是怎麼被執行的呢？首先，有一個叫做 IP 的暫存器會指向程式
開始的地方（通常是 main 函數），IP 的意思就是 Instruction Pointer，
CPU 會依序執行 IP 所指位址的指令。
當函數呼叫發生的時候，硬體必須經過下列的流程才能轉移控制權：
函數呼叫發生
↓
把目前的程式執行狀態存進 stack (含 IP)
↓
把函數的參數由右而左存進 stack
↓
把 IP 指向欲前往的函數
↓
前往函數
進入函數之後，函數由 stack 取得參數 (這部份的碼由編譯器自動產生)
之後，開始執行，執行完畢時依以下的流程交回控制權：
函數結束
↓
將傳回值存入 stack
↓
取出 stack 中原程式執行狀態
↓
恢復原程式執行狀態 (不含 IP)
↓
取出傳回值
↓
存回原來的 IP
↓
繼續執行原來的程式
我們每呼叫函數一次，都必須做這些動作，也就是 CPU 必須浪費很多時間
來處理這些記憶體的儲存和更新，會使程式的速度變慢，所以我們說遞迴
函數花費了太多的能量，因為遞迴函數就是不斷地執行函數的呼叫。
--
本文原作者為徐振家，原作刊載於星星神教總壇 ☆清華電機☆ test 板。
你可以以電子文件的形式將本文自由流傳於台灣學術網路，但必須包含此版權聲明。
原作者依中華民國著作權法之規定，享有本文之著作權，請勿抄襲以免觸法。
未經授權任何人不得以任何形式對本文做任何修改及商業上之應用。
其他網路的轉載或其他用途的應用，請先知會作者，並取得其同意。
對本文有任何疑問或意見請 mail 給 ax.bbs@bbs.ee.nthu.edu.tw，謝謝。