BBS水木清华站∶精华区

发信人: ax.bbs@bbs.ee.nthu.edu.tw. (athena), 信区: test
标  题: 星星流讲座 0042
发信站: ☆清华电机☆ (Tue Jul 18 22:54:26 1995)

第 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，谢谢。