物件導向程式設計 (Object-Oriented rogramming) 第 8 章 物件導向程式設計 (Object-Oriented rogramming)

本章重點 8 - 1 認識類別與物件 (自行研讀) 8 - 2 定義類別與建立物件 8 - 3 方法的進階應用 8 - 4 方法的多重定義 (Overloading) 8 - 5 綜合演練

8-1 認識類別與物件 如果將 Java 程式比擬為一齣舞台劇, 那麼要說明甚麼是物件導向程式語言就不難了。 要上演一齣舞台劇, 首先必須要有導演, 先將自己想要表達的理念構思好； 編劇負責將劇裡所需要的角色、道具描繪出來, 並且將這些元素搭配劇情撰寫出劇本； 最後, 再由演員以及道具在舞台上依據劇本實際的演出。 每一個 Java 程式也一樣可以分解為這些要素, 導演就是撰寫程式的您,要先設想程式想要完成甚麼事情。 接下來的編劇當然還是您, 必須先規劃出如何完成工作。

8-1-1 類別 (Class) 與物件 - Java 舞台劇的角色與演員 一齣舞台劇有了基本的構思之後, 接下來就要想像應該有哪些角色來展現這齣劇, 每一種角色都有它的特性以及要做的動作。 舉『西遊記』為例, 當然主角是美猴王, 它有多種表情、還能夠進行 72 變。除了美猴王以外, 當猴子猴孫的小猴子也少不了, 這些小猴子可能有 3 種表情, 而且可以東奔 西跑等等。

類別 (Class) 與物件 - Java 舞台劇的角色與演員 同樣的道理, 舞台上除了演員外, 可能還需要一些佈景或道具, 每一種佈景也有它的特性與可能的動作。舉例來說, 『西遊記』中美猴王騰雲駕霧, 舞台上可少不了雲。雲可能有不同顏色, 也可以飄來飄去, 而且同時間舞台上可能還需要很多朵雲。

類別 (Class) 與物件 - Java 舞台劇的角色與演員 不論是要演員演的、還是由道具來表現的, 以下我們通稱為角色。在劇本中就描述這些角色的特性與行為, 及全劇的進行, 然後再找演員或是製作道具來實際演出。 有些角色, 像是小猴子, 可能就會有好幾個, 就得找多個演員來演出同一個角色, 只是每一個猴子站的位置、表情不一樣。

類別 (Class) 與物件 - Java 舞台劇的角色與演員 在 Java 中, 每一種角色就稱為一種類別 (Class), 類別可以用來描述某種角色的屬性與行為； 在程式執行時演出這種角色的演員或道具就稱為此類別的物件 (Object ), 物件就依循類別所賦予的屬性與行為, 按照程式流程所描繪的劇本演出。 以下圖為例, 『小猴子』角色就是一種類別, 而小猴子 A、小猴子 B、小猴子 C 則分別是由不同演員扮演, 表情、位置各有不同的小猴子『物件』。

8-1-2 程式流程 - Java 舞台劇的劇本 構思好了各個角色後, 接著就是劇本了。哪個演員應該在甚麼時候上場、做甚麼動作、站在哪個位置、講甚麼話, 這些就是劇本應該描述清楚的內容。 其實劇本也就是整個舞台劇的流程, 描繪了每個演員的上場順序、對話內容先後、位置移動等等。 對於 Java 程式也是一樣, 第 5 、6 章所討論的流程控制正是為了安排 Java 程式執行時的順序, 也就是 Java 程式的劇本。 哪個物件應該在甚麼時候登場、各個物件在某個時候應該做甚麼動作？這些就是流程控制所要掌控的事情。有了流程控制, 所有的物件就照著劇本演出, 執行程式了。

8-1-3 main () 方法 – Java 舞台劇的舞台 舞台劇顧名思義, 當然要有個舞台, 讓各個演員能夠在上面演出。對 Java來說, 它的主要舞台就是 main() 方法。在第 2 章中曾經提到過, 每個 Java 程式都必須要有一個 main() 方法, 它也是 Java 程式執行的起點。 因此 main() 方法裡頭所撰寫的敘述, 就相當於 Java 程式的劇本, 而實際執行時, main() 方法就像是 Java 程式的舞台, 讓所有的物件依據流程一一登場。 類 別 屬 性(成員變數、欄位) 方 法(行為、動作) 學生 學號、系所、修課科目、成績 考試、通過、被當 電腦 品牌、CPU、記憶體、 開關機、執行程式 汽車 品牌、顏色、車牌號碼、載油量、耗油率 行駛

8-2 定義類別與建立物件 使用物件導向的方式設計 Java 程式時, 先要規劃、勾勒出要完成的工作, 接下來最重要的一件事就是擬定程式中需要哪些角色, 透過這些角色來執行所要達成的工作。 以 Java 的角度來說, 擬定角色也就是規劃出程式中要有哪些類別, 並且實際描述這些類別的特性與行為。

程式架構 JAVA3之程式架構 class 程式架構 Attribute(屬性區) class區 Method(方法區) Construction (建構方法區) class區 主程式區 (也是class) 程式架構 class Attribute(屬性區) Method(方法區) Construction (建構方法區)

程式架構 程序式語言 物件導向式語言 #include <stdio.h> #include <stdlib.h> int fun(int a) { return a-1; } int main() printf(“fun(3)=%d“, fun(3)); system(”pause”); return 0; import java.lang.*; class A{ int fun(int a) { return a-1; } public class ex1041101 { public static void main(String[] args){ A a = new A(); printf(“fun(3)=“+ a.fun(3));

8-2-1 定義類別 在Java中, 要描繪類別, 需使用 class 敘述, 其語法如下： Class name 類別名稱 Class body 類別本體 Attribute 屬性 Method 方法

定義類別 class 保留字後面跟著的就是所要定義的類別名稱, 接著是一個區塊, 這個區塊稱為類別本體 (Class Body), 其內容就是用來描述此類別的屬性與行為。 舉例來說, 我們要設計一個代表汽車的類別, 基本的結構如下： 無任何內容的空白類別

定義類別 宣告類別之後, 我們就可以用它來建立物件。 基本型別建立變數時, 會先宣告變數名稱, 再設定一個初始值給它。 而使用類別建立物件, 就如同用一個新的資料型別 (類別) 來建立一個類別變數 (物件), 比較特別的是, 必須用 new 運算子來建立物件： Java 2 Java 3 類別定義 宣告物件，產生物件 ….{ int x, y; x=5; y=10; x=x+y; } class Student { int number; int age; } ….. { Student ROBERT; ROBERT = new Student(); ROBERT.number=9702016; ROBERT.age= 52; } int, double…稱為基本資料型態(data type)宣告時即產生記憶體位置，可直接使用

定義類別 內部記憶體在搞什麼? Student ROBERT = new Student(); Class Student { 定義類別 內部記憶體在搞什麼? 類別定義 Student ROBERT = new Student(); Class Student { int number; int age; } 記憶體 記憶體 ….. { // Student ROBERT; // Student ROBERT = new Student(); ROBERT.number=9702016; ROBERT.age= 52; } ROBERT 1000 1000 9702016 number null 52 age 宣告物件，產生物件 參照 Reference NOTE： 1.參照(reference)：儲存記憶體位址 2.初始值： 基本資料型態：0，物件：null

定義類別 定義類別 程式中第 8 行先宣告了 2 個 Car 物件, 此部份和用基本型別宣告變數沒什麼不同。 當程式宣告基本型別的變數, Java 就會配置變數的記憶體空間；但是宣告物件時, Java 僅是建立了指向物件的參照 (程式中的 oldcar、newcar), 並不會實際配置物件的記憶體空間, 必須再如第 10、11 行使用 new運算子, 才會建立實際的物件。

定義類別 在 new 運算子後面, 呼叫了與類別同名的方法, 稱為建構方法(Constructor), 留待第9章再介紹。 呼叫建構方法時, Java 即會配置物件的記憶體空間, 並傳回該配置空間的位址。也可以將宣告和建立物件的敘述放在一起： 物件名稱 類別名稱 類別名稱

8-2-2 成員變數 - 類別的屬性 在類別中, 需使用成員變數 (Member Variable) 來描述類別的屬性, 在 Java語言中又稱其為類別的欄位 (Field)。成員變數的宣告方式, 和前幾章所用的一般變數差不多, 例如我們的汽車類別要有記錄載油量、耗油率, 可寫成：

成員變數 - 類別的屬性 有了成員變數時, 即可在程式中存取物件的成員變數, 存取成員變數的語法為： 有了成員變數時, 即可在程式中存取物件的成員變數, 存取成員變數的語法為： 小數點符號 (.) 【發音dot，翻譯「的」】 就是用來取得物件成員變數的運算子, 透過這個方式, 就能像存取一般變數一樣, 使用物件中的成員變數。 ROBERT.age：羅伯特的年齡

成員變數 - 類別的屬性 定義Car類別 宣告並產生物件 設定物件的 屬性初始值 列印物件 屬性訊息 在主程式中須註明是 哪一個物件的屬性

8-2-3 方法 (Method) - 類別的行為 要讓物件可做的動作, 就必須在類別中, 用方法(Method) 來描述物件的行為, 定義方法的語法如下： 方法名稱就代表類別可進行的動作, 而小括弧的部份稱為參數列, 列出此方法所需的參數。 參數的用途是將必要的資訊傳入方法之中, 若不需傳入任何資訊, 小括弧內可留空。 大括號 {} 的部份即為方法的本體, 就是用敘述組合成所要執行的動作, 當然也可以再呼叫其它的方法。 參數：可有可無！

方法 (Method) - 類別的行為 方法和運算式類似, 可以有一個運算結果, 這個運算結果稱為方法的傳回值（Return Value）。 在方法名稱前面的傳回值型別（Return Type）就標示了運算結果的型別, 例如 int 即表示方法會傳回一個整數型別的結果, 我們必須在方法本體中用 return 敘述將整數資料傳回： 重點： 1.有返回值型態時，須注意返回變數值(X)與傳回值型態(int)是否一致!! 2.在每個要回去的地方都要有return，通常是多重條件判斷或case switch指令

方法 (Method) - 類別的行為 如果方法不傳回任何結果, 可將方法的型別設為 void, 方法中也不必有 return 敘述。 要在 main() 方法中呼叫類別的方法, 與存取成員變數一樣, 都是用小數點, 例如：『物件.方法名稱()』。 呼叫方法時, 程式執行流程會跳到此方法本體中的第一個敘述開始執行, 一直到整個本體結束或是遇到 return 敘述為止, 然後再跳回原處繼續執行。 方法的定義 執行方法本體 跳至方法本體 第一行執行 返回呼叫指令 下一行繼續執行 呼叫方法

class member method 在方法定義中不指明哪一個物件的屬性!! 誰來叫，就印誰

方法 (Method) - 類別的行為 這個程式的執行結果和前一個範例 BuildCar2.java 相同, 但我們將輸出汽車資訊的相關敘述, 設計成方法。 第 5〜10 行就是代表取得物件狀態的 printState() 方法, 其傳回值型別為void, 表示這個方法不會有運算結果。另外, 方法名稱後面的小括號是空的, 也表示使用這個方法時並不需要傳入任何資訊。 第 7、9 行存取類別的成員變數時, 不像前一個範例還有加上物件名稱。這是因為物件在呼叫方法時, 方法中存取的就是該物件的屬性, 所以直接指定成員變數的名稱即可。 第 21 行即以『物件.方法名稱()』的語法呼叫方法, 由於方法會取得目前呼叫物件 (此處為 oldcar) 的屬性, 所以 printState() 方法所輸出的, 就是在第17 、18 行所設定的值。

各自獨立的物件 前面說過類別就像是角色, 我們可以找多位演員來演出, 但他們彼此都是獨立的, 擁有各自的屬性。 前面的範例都只建立一個物件, 所以體會不出類別與物件的差異, 如果我們建立多個物件, 並分別設定不同的屬性, 就能看出每個物件是獨立的, 每個物件都會有各自的屬性 (成員變數), 互不相干：

gas oldcar eff gas newcar eff

各自獨立的物件 在第 15、16 行時分別建立了 2 個物件, 接著設定其成員變數的值, 最後在第 24 、26 行呼叫 printState() 方法。 由執行結果可看出, 兩個物件各自擁有一份 gas、eff 成員變數, 互不相干。

物件變數都是參照 由於物件是參照型別, 因此也和陣列一樣, 做指定運算及變更成員變數值時, 要特別清楚參照與實際物件的差異。例如：

3 a.x a 10 3 b.x b c.x c a==b? false c==b? true

物件變數都是參照【裡面存的是記憶體位址】 範例中的 Test 類別是個陽春的類別, 其中只有一個變數 x, 以及一個顯示 x 值的 show() 方法。在 main() 方法中則宣告了 3 個 Test 類別的變數, 以下有幾點需要說明： 由於 a 與 b 是分別使用new算符產生的物件, 因此 a 與 b 是指到不同的物件；在第 16 行用 == 算符比較 a 與 b 時, 比較的是參照值, 所以結果是false。 相同的道理, 第 18 行將 b 指定給 c 時, 是將 b 的參照值指定給 c, 所以變成c 與 b 的參照都指向同一個物件, 因此第 20 行 c == b 的比較結果自然就是 true。 因為 c 和 b 指向同樣的物件, 所以第 19 行修改 c.x 後, 再透過 b 存取成員x 時, 存取到的就是同一個物件的成員 x, 也就是修改後的值。

建立物件陣列 建立多個物件時, 也可用陣列的方式來建立, 每個陣列元素就是一個物件, 例如：

建立物件陣列 程式在第 15 行以 Car 為資料型別, 宣告了一個陣列 ManyCars, 但這行敘述也只是配置陣列的空間, 並未配置物件空間。 所以在第 17 行的 for 迴圈中, 就再用 new 運算子依序為陣列中每個元素, 配置物件空間, 同時設定其成員變數的值。第 23 行的 for 迴圈則只是依序輸出物件的內容。

8-2-5 物件的銷毀與回收 物件也和陣列一樣, 受到 Java 的監控, 可以在不再需要時自動回收。 這個監控的方式一樣是使用參照計數, 每個物件都有一個參照計數, 只要有任何一個變數儲存了指向某物件的參照, 這個物件的參照計數就會增加 1 。 物件的參照計數會在以下 3 種狀況下減 1：

物件的銷毀與回收 強迫釋放參照：當您把參照型別的變數指定為 null 值時, 就表示這個變數不再需要使用所指向的物件, 這時所指向物件的參照計數便會減 1。 將變數指向別的物件：如果您將變數指向別的物件, 那麼也就表示往後不再參照到原來的物件, 因此原本的物件的參照計數也會減 1。 離開有效範圍：當參照型別的變數離開有效範圍時 一旦參照計數的值變為 0 時, Java就會將該物件列為可以回收的對象, 並且在適當的時機將之回收, 避免這種不再會被使用到的物件佔用記憶體空間。

8-3-1 方法的參數 我們可將類別的方法, 設計成在呼叫時可指定參數, 以便將必要的資訊傳入方法中, 讓它可做不同的動作或處理。 舉例來說, 要為我們的汽車類別設計一個代表行駛的方法 move(), 即可用要行走的『里程數』為參數, 讓物件行走指定的里程：

方法的參數 第 12 行定義的 move() 方法有一個 double 型別的參數, 在方法中則先判斷目前油量是否足夠行駛指定的里程, 足夠才將載油量減去行駛所需的油量,並輸出行駛的訊息。 在第 28 行即以里程數為參數, 呼叫 move() 方法。在此提醒大家, 呼叫時可使用任何型別相符的變數或運算式。 使用方法時要特別注意以下兩點： 呼叫時的參數型別必須與方法定義中的『型別一致』。如果呼叫時的參數型別與定義的型別不符, 除非該參數可依第 4 章的描述, 自動轉型為方法定義的型別, 否則就必須自行做強制轉型。 呼叫時的參數數量必須和方法定義的參數『數量一致』。例如剛才示範的 move() 方法定義了一個參數, 若呼叫時未加參數或使用 2 個參數, 編譯時都會出現錯誤。

8-3-2 方法傳回值 除了將資料傳入方法外, 我們可以更進一步讓方法傳回處理的結果。回顧一下前面介紹過的方法定義語法, 要有傳回值時, 除需定義方法的型別外,也要在方法本體中用 return 敘述, 將處理結果傳回：

方法傳回值 return 敘述的傳回值, 可以是任何符合資料型別的變數或運算式, 當然在必要時, Java 會自動做型別轉換。例如上例中的 int, 則傳回值需為 int、long、float、double, 但如果程式中傳回的是 short 型別, 編譯時會發生錯誤, 必須自行將之強制轉為 int 型別。 以下範例就將前面的 move() 方法加上傳回值, 讓它會傳回實際行駛的里程數：

（剩95公升） （剩45公升） （剩 0公升）

方法傳回值 第 12 行的 move() 方法宣告為會傳回 double 型別, 方法內容也較先前做了些修改：首先仍是判斷油量是否足夠, 是就將載油量減去耗油量, 並傳回行駛里程；若油量不足, 則計算出剩餘油量能走幾公里, 並將載油量減去耗掉的油量, 並傳回實際行駛里程。 在 main() 方法中第 33〜35 行連結呼叫 3 次 move() 方法, 但由執行結果可看到, 第 3 次呼叫時雖指定要走 5000 公里, 但因油量不足, 所以只走了 450公里。

8-3-3 參數的傳遞 前面我們提到過, 在叫用方法時, 可以透過參數傳入資訊, 這有幾點需要注意, 我們分別在以下說明之。 參數是傳值方式（Call By Value）傳遞 傳遞參照型別的資料 (Call By Reference)

參數是傳值方式（Call By Value）傳遞 參數在傳遞時, 是將值複製給參數, 請看以下範例：

參數是傳值方式（Call By Value）傳遞

參數是傳值方式（Call By Value）傳遞 第 7 行呼叫 changePara() 方法時以 i 為參數, 實際上是將 i 的值 20 指定給changePara() 中的 x, 因此 x 與 main() 中的 i 是兩個獨立的變數。 所以 changePara() 修改 x 的值, 對 i 完全沒有影響。

傳遞參照型別的資料 (Call By Reference) 如果傳遞的是參照型別的資料, 雖然傳遞的規則不變, 卻會因為參照型別為記憶體位址這項特性, 使執行的效果完全不同, 如下範例：

傳遞參照型別的資料 (Call By Reference) 在第 21 行呼叫 changeTestA() 方法時所用的參數是物件 a, 但我們前面已提過, 物件變數都是指向物件的參照, 所以傳入方法時所『複製』到的值, 仍是同一物件的參照值。 也就是說, 第 10 行的參數 t 和 main() 方法中的變數 a現在都指向同一個物件, 所以透過 t 更改物件的內容後, 再透過 a 存取時就已經是修改過後的內容了。

8-3-4 變數的有效範圍（Scope） 在 Java 程式中, 可以在任何需要的地方宣告變數。每一個變數從宣告之後, 並非就永遠可用, Java制訂有一套規則, 定義了一個變數能夠被使用的區間, 這個區間就稱為變數的有效範圍。 以下將分別說明 宣告在方法內的變數、 方法的參數、 宣告在類別中的成員變數、以及 迴圈中所宣告的變數之有效範圍。

方法內的區域變數 （Local Variables） 宣告在方法內的變數, 稱之為區域變數。這是因為區域變數只在流程進入其宣告所在的程式區塊後, 才會存在, 並且要指定初始值後才生效可以使用。 此後區域變數便依附在包含它的最內層區塊中,一旦流程離開該區塊, 區域變數便失效了。正因為此種變數僅依附於所屬區塊的特性, 所以稱為『區域』變數。 要注意的是, 區域變數生效之後, 如果流程進入內含的區塊, 那麼該區域變數仍然有效, 也就是在任一區塊中的程式可以使用外圍區塊中已經生效的變數。 因為如此, 所以在內層的區塊不能再以外層區塊的變數名稱宣告變數。舉例來說：

方法內的區域變數 （Local Variables）

方法內的區域變數 （Local Variables） 從執行結果可以看到, 內層的區塊可以使用到外層區塊中已經生效的變數。 但要特別注意, 雖然外層區塊宣告了和內層區塊同名的變數 (例如第 7行和第 14 行的 z), 但是在流程執行到第 14 行時, 第 7 行的變數 z 所在的區塊已經結束, 因此變數 z 已經失效, 所以可以在第 14 行使用相同的名稱宣告變數了。 但是如果把第 14 行移到原本的第 7 行之前：

方法內的區域變數 （Local Variables）

方法內的區域變數 （Local Variables） 編譯時就會發生錯誤, 告訴我們變數 z 已經定義了, 不能重複宣告： 宣告在方法中的參數, 在整個方法的主體中都有效, 因此我們不能在方法主體中宣告和參數同名的區域變數。

宣告在類別中的成員 類別中的成員是依附於實體的物件, 一旦依據某個類別產生物件後, 這個物件就擁有一份成員變數。只要該物件未被銷毀, 這一份成員變數就依然有效, 例如：

宣告在類別中的成員 在第 5、6行中, show() 方法可以使用到 Test 類別的成員變數 x、y, 即便 y 是在 show() 方法之後才宣告, 也一樣可以使用。 但要注意, 如果方法中宣告了和類別成員同名的變數或是參數, 此時方法中的變數優先於類別中的成員, 也就是說, 使用到的是方法中的變數, 而不是類別的成員。這個效應稱為名稱遮蔽 (Shadowing of Name)。例如：

宣告在類別中的成員

宣告在類別中的成員 在第 5 行的 show() 方法中, 將參數取名為 x, 它會遮蔽掉成員變數 x；同理, 在第 6 行宣告的區域變數 y, 則會遮蔽掉成員變數 y, 所以 show() 方法顯示的 x、y 值不是物件的成員變數值, 而是方法中的參數 x 與區域變數 y。 在這種情況下, 如果需要存取成員變數 x 與 y, 就必須使用 this 保留字,其語法為『this.成員變數』。this 代表的是『目前物件』的參照, 所以『this.成員變數』可存取到目前物件的成員變數。

宣告在類別中的成員

宣告在類別中的成員 由於 this 保留字是『目前物件』的參照, 所以在第 15 行用物件 a 呼叫show() 方法時, 程式流程進入第 5 行的 show() 方法時, this 就是物件 a 的參照,所以執行第 7、8 行的 this.x 、this.y, 就相當於 a.x、a.y。 所以最後顯示出來的, 就是物件 a 的 x 與 y 成員變數的值, 而不是方法中的參數以及區域變數。

宣告在 for 迴圈中的變數 在使用 for 迴圈的時候, 通常都是在 for 的初始運算式中宣告迴圈變數,此時這個迴圈變數就只在整個 for 區塊中有效, 一旦離開 for 迴圈時, 該變數也就無法使用了 (相同的規則也適用於 foreach 迴圈)。 如果需在迴圈結束後取得迴圈變數的值, 就必須在 for 迴圈之前自行宣告變數, 例如：

宣告在 for 迴圈中的變數

宣告在 for 迴圈中的變數 如果您把 i 宣告在 for 迴圈中, 像是這樣：

宣告在 for 迴圈中的變數 編譯時就會發生錯誤： 告訴您無法找到變數i 。這是因為在第 7 行時, 前面的 for 迴圈區塊已經結束, 因此在 for 中宣告的變數 i 也已經失效了。

8-3-5 匿名陣列 (Anonymous Array) 在呼叫方法時, 如果所需的參數是陣列, 那麼往往就必須要先宣告一個陣列變數, 然後才能傳遞給方法。 如果在呼叫方法之後就不再需要使用該陣列, 就表示這個陣列除了作為參數傳遞以外, 並沒有其他的用途, 這時要為陣列變數取個好名字就有點困難。請先看看以下的程式：

匿名陣列 (Anonymous Array) 在第 13 ~ 15 行就是為了要呼叫 showMultipleString() 方法, 而特別宣告的strs 陣列, strs 這樣的名稱很顯然沒有甚麼意義。 為了應付這類需求, Java 就設計了一種稱為匿名陣列的方式, 可以讓您不需宣告陣列變數, 就可以建立並傳遞陣列。我們可以將剛剛的程式改寫如下：

匿名陣列 (Anonymous Array)

匿名陣列 (Anonymous Array) 第 14 行就是建立匿名陣列, 只要使用 new 運算子, 接著陣列元素的型別,以及一對中括號, 再跟著指定陣列的初值即可。這樣一來, 就不需要為了陣列變數的名字而憂心了。

8-3-6 遞迴 (Recursive) 在使用方法時, 有一種特別的用法稱為遞迴。簡單來說, 遞迴的意思就是在方法中呼叫自己。例如, 如果要計算階乘 (Factorial), 它的定義如下： 換個角度來思考, 也可以把階乘定義如下： 也就是說, 當 x 為 0, x! 的值就是 1；否則 x! 的值就是 x 乘上(x - 1)!。依據此規則, 寫成程式就如下

[Q] 數列形：1,1,2,3,5,8,13,…求第10項 解析 從第三項開始，為前2項之和 假設第n項表是為 f(n) 終止條件 遞迴公式 f(3)= f(2)+ f(1) f(4)= f(3)+ f(2) .… f(n)= f(n-1)+ f(n-2) 程式 Class Recursion{ int f(int n){ if(n<=2) { return 1; } else { return f(n-1)+ f(n-2); 主程式 Recursion a = new Recursion(); System.out.println(“f(10)=“+ a.f(10));

[Q]函數型 解析 從第三項開始，為前2項之和 假設第n項表是為 f(n) 終止條件 f(1) = 1 f(2) = 2 遞迴公式 f(3)= f(2)+ f(1) f(4)= f(3)+ f(2) .… f(n)= 2f(n-1)+ 3f(n-2) +4

[Q]累積型1 ： 解析 從第三項開始，為前2項之和 假設第n項表是為 f(n) 終止條件 f(1) = 1 遞迴公式 f(2) = 1+1/2= f(1) +1/2 f(3)= 1+1/2 +1/3 = f(2)+ 1/3 f(4)= 1+1/2 +1/3 +1/4 = f(3)+ 1/4 .… f(n)= f(n-1)+ 1/n

[Q]累積型1 ： 解析 從第三項開始，為前2項之和 假設第n項表是為 f(n) 終止條件 f(1) = 1 遞迴公式 f(2) = 1-1/2= f(1) -1/2 f(3)= 1-1/2 +1/3 = f(2)+ 1/3 f(4)= 1-1/2 +1/3 -1/4 = f(3)- 1/4 .… 程式 Class Recursion{ double f(int n){ if(n==1) { return 1; } else if(n%2==0) { return f(n-1) – 1.0/n else { return f(n-1) + 1.0/n; 主程式 Recursion a = new Recursion(); System.out.println(“f(10)=“+ a.f(10)); 79

遞迴 (Recursive)

遞迴 (Recursive) Computer 類別提供了 factorial() 方法計算階乘, 其計算方法就是依循前面的定義： 第 5 行檢查 x 是否小於或等於 1, 這是為了防範使用者輸入負數或是 0,如果是, 就直接傳回 1。 當 x 大於 1 , 就呼叫自己計算 (x - 1)!, 並傳回 x * (x - 1)!。

遞迴 (Recursive) 使用遞迴時, 最重要的一點就是結束遞迴的條件, 也就是不再呼叫自己的條件。 以 Factorial.java 為例, 這個條件就是 x 是否等於 0, 此條件成立時直接傳回 1, 而不再呼叫自己。如果缺少了這個條件, 程式就會不斷地呼叫自己, 無法結束程式了。 這就像是使用迴圈時忘了加上結束迴圈的條件, 使得迴圈沒完沒了一樣。

分而治之 (Divide and Conquer)（個別擊破） 遞迴非常適合用來處理可以分解部分個別處理、再統合結果的問題。 像是剛剛的階乘計算, 就是把原來的問題每次縮小 1, 直到可以直接取得結果之後, 再回頭一步步計算出整體的結果。這種解決問題的方式, 稱為分而治之 (Divide and Conquer)。 以上一章介紹過的二分搜尋法來說, 就很適合透過遞迴的方式來處理。二分搜尋法的規則如下：

分而治之 (Divide and Conquer) 如果中間的元素就是要找的資料, 那就找到了。 如果中間的元素比要找的資料小, 那資料只可能出現在右半邊。 否則資料只可能出現在左半邊。 依據此規則, 就可以將上一章的二分搜尋法以遞迴方式改寫：找出15的位置 high middle low 30

分而治之 (Divide and Conquer)

分而治之 (Divide and Conquer)

分而治之 (Divide and Conquer)

分而治之 (Divide and Conquer)

分而治之 (Divide and Conquer) Searcher 類別的 search() 方法, 就透過 binarySearch() 方法, 以遞迴的方式進行二分搜尋。 其中 low 與 high 參數代表要搜尋的區間, 因此遞迴的結束條件之一就是第 13 行的狀況, low 比 high 大, 表示已經搜尋完畢, 但找不到資料。

分而治之 (Divide and Conquer) 遞迴結束的條件之二就是中間元素即為所要找的資料, 此時就傳回中間元素的索引碼。如果以上條件均不成立, 表示還可繼續找下去, 所以第 22 行便先與中間元素比較。 如果要找的資料比中間元素大, 那麼就遞迴呼叫自己,尋找右半區間；否則, 就遞迴呼叫自己尋找左半邊。

分而治之 (Divide and Conquer) 往後大家還會看到許多適合採用遞迴處理的問題, 這些問題以遞迴的觀念思考時, 往往會變得很簡單, 但如果不使用遞迴, 程式就會變得異常複雜。 因此,熟悉並善加運用遞迴就成為程式設計時的一門學問, 建議您最好反覆的練習。

補充：命名規則 Package（套件） 英文單字全部小寫，e.g. java.lang Class（類別） 每個英文單字的第一個字母大寫，e.g. Car, StuDeUniversity Interface（介面） 與class(類別)相同 Attribute / member / field（屬性） 英文單字的第一個字母小寫，其它單字第一個字母大寫，e.g. numberOfLegs Boolean 屬性值習慣用isXXXX來命名 Method（方法） 與attribute(屬性)相同，但後面有小刮號()，e.g. eatMeat() Constant（常數） 英文單字全部大寫，單字之間以底線(＿)連接，e.g. MAX_LEGS

8-4 方法的多重定義 (Overloading) 如果您仔細閱讀過本書到目前為止的範例程式, 可能已經發現到一件奇怪的事, 我們使用過最多的 System.out.println() 方法顯然和之前所說明的規則抵觸。 在 8-3-1 中『方法的參數』這一小節曾經提到, 呼叫方法時, 傳入的參數個數與型別必須和方法的宣告一致。 可是在範例程式中, 不論變數 x 是哪一種型別, 都可以傳入 System.out.println() 方法, 列印出變數的內容, 例如：

方法的多重定義 (Overloading)

方法的多重定義 (Overloading) 在第 9 ~ 12 行中, 分別傳入 int、double、String、boolean 型別的參數呼叫 System.out.println(), 都可以正常編譯。 這個方法的參數怎麼會這麼神奇, 可以同時是多種型別呢？在這一節中就要討論讓 System.out.println() 方法具有此項能力的機制 - 多重定義。

8-4-1 定義同名方法 由於實際在撰寫程式時, 常常會遇到類似意義的動作, 但因為處理的對象型別不一樣而有差異的狀況。因此, Java 允許您在同一個類別中, 定義參數個數或是型別不同的同名方法, 稱為多重定義 (Overloading)。 其實 Java 並不僅只是以『名稱』來辨識方法, 當 Java 編譯程式時, 也會將參數型別、參數數量等資訊, 都一併加到方法的簽名 (Method Signature)。當我們呼叫方法時, Java 就會依據方法簽名, 找出正確的方法。

定義同名方法 請看看這個例子。為了要撰寫一個計算矩形的方法, 我們常常會苦惱於要以長、寬來表示矩形, 還是要以左上角及右下角的座標來表示。若是採用多重定義的方式, 就可分別為不同的矩形表示法撰寫其適用的版本, 這樣不論是使用長寬還是座標都可以計算出面積。

定義同名方法

定義同名方法 這個程式在 Test 類別中定義了兩個同名的方法, 分別使用寬高以及座標的方式來描述矩形, 而兩個方法都傳回計算所得的面積。在 main() 方法中, 就利用不同的參數分別呼叫了這兩個版本的同名方法。

8-4-2 多重定義方法時的注意事項 在使用多重定義時, 有幾點是必須要注意的： 要讓同名方法有不同的簽名, 一定要讓參數型別或數量不同。不管是參數數量不同；或是參數數量相同, 但至少有一個參數型別不同, 都可讓編譯器為方法產生不同的簽名。而在呼叫方法時, Java 也能依簽名找出正確的版本。 參數的名稱及傳回值型別, 都不會是簽名的一部份。所以當類別中兩個方法的參數型別及數量完全相同時, 就算參數名稱或傳回值型別不同, 也會因簽名相同, 而產生編譯錯誤。

8-5 綜合演練 8-5-1 求乘方 許多數學問題都可以使用遞迴的觀念來定義, 除了之前已經看過的階乘以外, 求算乘方也一樣適用。x y 可以定義如下：

求乘方 寫成程式就如下：

求乘方

8-5-2 Fibonacci 數列 數學上還有一個有趣的數列, 稱為 Fibonacci 數列, 這個數列的定義是這樣的： 看到了嗎？這又是一個遞迴的定義。要依據這樣的定義寫出程式是很簡單的, 請看：

Fibonacci 數列

Fibonacci 數列

8-5-3 快速排序法 (Quick Sort ) 在第 7 章曾經介紹過使用氣泡排序法來為陣列元素排序, 在這一節中我們要以遞迴的技巧來排序, 介紹快速排序法。 快速排序法的想法是這樣的, 如果能夠把陣列安排成兩段, 前段的元素都比後段的元素小, 那麼接下來就可以把兩段元素看成是兩個單獨的陣列,只要將前後兩段分別排好序, 就等於整個陣列排好序了。 前後兩段的排序自然可以再遞迴套用快速排序法, 分解下去到每一段只有 1 個元素時, 自然就不需要排序。

快速排序法 (Quick Sort ) 現在的問題就在於如何才能把陣列安排為 2 段, 而且前一段的元素會比後一段的元素都小？這裡採用一個很簡單的作法： 首先找出陣列中間的元素, 記住它的值。 從陣列的頭往尾端搜尋, 當遇到一個比中間元素還大的元素就先停住。 從陣列的尾端往頭搜尋, 當遇到一個比中間元素還小的元素時就先停住。 將第 2 與第 3 步驟找到的元素互換。

快速排序法 (Quick Sort ) 反覆進行 2 ~ 4 的步驟, 一直到兩端的搜尋相遇為止。這時, 相遇的地方就可以將陣列切成兩段, 前段的值都比後段的值要小。 寫成程式如下：

快速排序法 (Quick Sort )

快速排序法 (Quick Sort )

快速排序法 (Quick Sort )

快速排序法 (Quick Sort )

快速排序法 (Quick Sort )

快速排序法 (Quick Sort )

快速排序法 (Quick Sort ) 06 ~ 08 就是遞迴結束的條件, 如果只有一個元素, 當然不需要排序, 直接返回。 17 ~ 19 以及 21 ~ 24 行分別就是想法中的第 2 及第 3 步驟。 27 ~ 34 就是交換元素的步驟。 38 、39 行則分別遞迴呼叫自己來為前後兩段元素排序。

8-5-4 河內之塔遊戲 (Hanoi Tower) 河內之塔遊戲是在 1883 年由法國的數學家 Edouard Lucas 教授所提出。話說在古印度神廟中有 3 根柱子, 分別稱之為 A、B、C, 在 A 這根柱子上有64 片由大至小往上相疊的碟子, 如果有人能夠謹守較大的碟子不能疊到較小的碟子上的規定, 將這些碟子藉由柱子 B 的幫助, 由柱子 A 全部移到柱子 C的話, 世界末日就會降臨。

河內之塔遊戲 (Hanoi Tower) 我們準備撰寫一個程式來看看如何完成搬運碟子的工作。要解決這個問題, 基本的想法是如果能夠將最大的碟子留在 A, 而遵守規則將其餘的碟子透過 C 搬到 B 的話, 就可以將最大的碟子搬到 C, 接著只要再想辦法遵守規則將 B 中的碟子搬到 C 就完成了。

河內之塔遊戲 (Hanoi Tower) 這樣問題就被分解為： 先將除了最大的碟子以外的 63 個碟子透過 C 搬到 B。 將最大的碟子由 A 搬到 C。 將 B 中的 63 個碟子透過 A 搬到 C。

河內之塔遊戲 (Hanoi Tower) 有沒有看出來這裡面的遞迴味道？第 1 與第 3 項的工作其實就是少了一個碟子的河內之塔遊戲, 如果有一個解決河內之塔的方法, 那麼第 1 和第3 項工作就是遞迴呼叫同一個方法, 只是碟子少一個而已。 接下來的關鍵就在於這個遞迴方法的結束條件。很簡單, 如果只有 1 個碟子, 那麼就直接將碟子搬到目的地的柱子去, 而不需要遞迴呼叫方法。瞭解了這些觀念後, 就可以寫出描述搬移碟子的程式了：

河內之塔遊戲 (Hanoi Tower)

河內之塔遊戲 (Hanoi Tower)

河內之塔遊戲 (Hanoi Tower)

河內之塔遊戲 (Hanoi Tower)

河內之塔遊戲 (Hanoi Tower) HanoiTowerGame 類別的 go() 方法會呼叫 hanoiTower()方法來解決河內之塔問題, 為了簡化說明起見, 這裡顯示的是僅有 3 個碟子的執行結果。 hanoiTower() 方法就依循了之前所提出的解題概念, 先看看是否僅有 1 個碟子, 如果是就直接搬動；否則, 就遞迴先將最大的碟子之上的碟子都先搬走, 再將最大的碟子搬到目的地, 然後再將先前搬走的碟子搬到目的地。

河內之塔遊戲 (Hanoi Tower) moveDisc() 方法就是實際搬碟子的動作, 此處是以顯示訊息來表示。 透過遞迴的技巧, 寫起程式來不但簡單, 而且也和我們解題的思考方式一致, 迅速的解決了問題。