第 二 章 遞迴(Recursion) 課程名稱：資料結構 授課老師：________ 2019/5/5

本章學習目標 1.讓讀者了解遞迴的使用及條件，進而設計比較簡潔的程式。 2.讓讀者了解如何利用遞迴函數來解決典型的河內塔問題。 2019/5/5

本章內容 2-1遞迴(Recursion) 2-2 遞迴函數 2-3 遞迴的應用 2-4 遞迴與非遞迴的比較 2019/5/5

2-1 遞迴(Recursion) 何謂「遞迴(Recursion)」是指函式本身又可以呼叫自己的副程式。 我們在撰寫程式時，如果適時的使用遞迴方式，將可以使得程式 變得比較簡潔，但是，在撰寫時必須要先了解題意，並且要非常 謹慎小心使用，否則很容易產生無窮迴圈或無法預期的錯誤。 2019/5/5

例如：我們設計一個遞迴程式來計算n!時，如果沒有設定「終止狀況」(Termination Condition)時，將會無限制地呼叫自己，因此，就會造成無窮迴圈現象。 2019/5/5

在目前的程式語言中，並非每一種程式語言都具有遞迴呼叫的功能，例如： (1)不具遞迴呼叫的程式語言：BASIC, FORTRAN,COBOL等。 (2)具遞迴呼叫的程式語言：C, C++, PASCAL等。 2019/5/5

2-2 遞迴函數 如果撰寫程式來處理程序時，並且將程式模組化為一支獨立的函數，如果該函數可以反覆地自己呼叫自己，因此我們稱這個函數為「遞迴函數」。 在遞迴函數中，最典型的例子就是計算n階層的程式。 2019/5/5

一、數學上：n階層的概念如下： 說明：在撰寫一個n階層的遞迴函數程式時，則該函數將具備兩個主要特徵： 1.該遞迴函數可以自己反覆地呼叫自己 (4)參數的值會逐次遞減。 2.當參數值等於1時，必須停止遞迴呼叫。 2019/5/5

二、演算法上：n階層的概念如下： 2019/5/5

三、以圖解來說明：遞迴函數呼叫的過程 圖2-1 遞迴函數呼叫的過程 2019/5/5

四、遞迴函數種類 2019/5/5

2-3 遞迴的應用 遞迴在實務上的應用非常的廣，例如：計算n階乘(n!)、費氏數列、河內塔的圓盤搬移過程、求兩個正整數的最大公因數、二項係數等等。 2019/5/5

2-3.1 n階乘(n!) 利用遞迴方式來撰寫n階乘(n!)的程式。 2019/5/5

2-3.2 費氏數列 利用遞迴方式來撰寫Fibonacci Number(費氏數)的程式。 【定義】某一數列的第零項為0，第1項為1，其它每一個數列中項 目的值是由本身前面兩項的值之和。 2019/5/5

一、數學上：Fibonacci(費氏數)的概念 2019/5/5

二、演算法上：Fibonacci(費氏數)的概念 2019/5/5

2-3.3 最大公因數 一般在數學上找出最大公因數(Great Command Divisor)，大多是利用尤拉的輾轉相除法，而輾轉相除法, 又名「歐幾里德演算法」（Euclidean algorithm）乃求兩數之最大公因數演算法。即利用兩數反覆相除，直到結果不為0時，將取其不為0的餘數。 2019/5/5

【演算法】 2019/5/5

【舉例】 以下範例說明輾轉相除法過程：以18及15為例，必須要利用「輾轉 相除法」，求最大公因數。其概念如下所示： 2019/5/5

2-3.4 河內塔問題 假設有A、B、C三根柱子，A柱子上有3個直徑大小不一的中空盤子，由大而小疊放在一起，如下圖(3個盤子)所示。試問最少需要搬多少次，方能將這些盤子從A柱搬到C柱？ 【規則】1.一次只能移動一個盤子。 2.在搬移過程中，小的盤子不能放在大的盤子下方。如圖2-2所示。 2019/5/5

【重要觀念】 2019/5/5

2019/5/5

2019/5/5

【老師上課動態展示】檔案在附書光碟中。 2019/5/5

【演算法分析】 時間複雜度的計算是以執行了多少次搬動來計算,那麼T(n)等於多少呢？可由下列方式推演： 說明：當有n個盤子要搬動時，總共要搬動2n-1次， 所以可以說此問題的時間複雜度是O(2n)。 2019/5/5

2-3.5 二項式(Binomial)係數 二項式係數(Binomial Coefficient)來計算是根據Binomial理論，其計算公式為： 一般而言，二項式係數在數學上是應用於計算從m個球中取出n個球的排列組合的問題，目前台灣正熱門的運動彩的下注問題，就可以利用二項式來求算機率的問題。 2019/5/5

【數學與演算法之表示式】 2019/5/5

【舉例】利用遞迴求「二項式係數」之程式 2019/5/5

2-3.6 Ackermann’s Function 2019/5/5

【演算法】 Ackermann’s function在數學上的定義如下： 2019/5/5

【舉例】 利用遞迴求「Ackermann’s function」之程式 2019/5/5

2-4 遞迴與非遞迴的比較 何謂的「非遞迴(Non-recursion)」是指函數本身沒有呼叫自己的程式。 2-4 遞迴與非遞迴的比較 何謂的「非遞迴(Non-recursion)」是指函數本身沒有呼叫自己的程式。 遞迴雖然可以使用少數幾行的敘述就可解決複雜的問題，但有些問題會導致花更多的時間，因此在何時使用遞迴是很重要的。 2019/5/5

【遞迴函數的優、缺點】 2019/5/5

2019/5/5