5.1 一些一些遞迴的基本範例 5.2 一個典型的遞迴範例：河內塔 5.3 另一個範例：八個皇后 5-4 何時不要使用遞迴？

Presentation on theme: "5.1 一些一些遞迴的基本範例 5.2 一個典型的遞迴範例：河內塔 5.3 另一個範例：八個皇后 5-4 何時不要使用遞迴？"— Presentation transcript:

1 5.1 一些一些遞迴的基本範例 5.2 一個典型的遞迴範例：河內塔 5.3 另一個範例：八個皇后 5-4 何時不要使用遞迴？
Chapter 5 遞迴 5.1 一些一些遞迴的基本範例 5.2 一個典型的遞迴範例：河內塔 5.3 另一個範例：八個皇后 5-4 何時不要使用遞迴？

2 遞迴 在程式設計中，我們有時會利用遞迴以解決某些問題，既經濟又方便。 遞迴是一項比較抽象的課題，因此它隱含地利用了堆疊做為其存放暫時資料的場所，使得它給人有一種神祕的感覺。

3 5.1 一些遞迴的基本範例 一個呼叫它本身的函數稱為遞迴（Recursive）。在撰寫程式中，也常常會應用遞迴來處理某些問題，而這些問題通常有相同規則的性質，如求n!

4 5.1 一些遞迴的基本範例 從上述得知其相同的規則為某一數A的階層為本身A乘以（A減1）階層，依循此規則即可求出。

5 5.1 一些遞迴的基本範例 在撰寫遞迴時，千萬要記住必須有一結束點，使得函數得以往上追溯回去。如上例中，當n=1時，1!=1即為其結束點。
5.1 一些遞迴的基本範例 在撰寫遞迴時，千萬要記住必須有一結束點，使得函數得以往上追溯回去。如上例中，當n=1時，1!=1即為其結束點。 若以圖形表示n!階層的做法；假設n=4，其步驟如下（注意箭頭所指的方向）：

6 5.1 一些遞迴的基本範例

7 5.1 一些遞迴的基本範例 其實編譯程式在處理遞迴時，會藉助堆疊將呼叫本身函數的下一個敘述位址儲存起來，待執行完結束點後，再將堆疊的資料一一的彈出來處理。

8 5.2 一個典型的遞迴範例：河內塔 十九世紀在歐洲有一遊戲稱為河內塔（Towers of Hanoi），有64個大小不同的金盤子，三個鑲鑽石的柱子分別為A、B、C，今想把64個金盤子從A柱子移至C柱子，但可以借助B柱子，遊戲規則為： 每次只能搬一個盤子； 盤子有大小之分，而且大盤子在下，小盤子在上。

9 5.2 一個典型的遞迴範例：河內塔 假設有n個金盤子（1, 2, 3, ..., n），數字愈大表示重量愈重，其搬移的演算法如下： 否則
5.2 一個典型的遞迴範例：河內塔 假設有n個金盤子（1, 2, 3, ..., n），數字愈大表示重量愈重，其搬移的演算法如下： 假使n=1則 搬移第1個盤子從A至C 否則 搬移n-1個盤子從A至B 搬移第n個盤子從A至C 搬移n-1個盤子從B至C

10 5.2 一個典型的遞迴範例：河內塔 假設以3個金盤子為例：從A柱子搬到C柱子，而B為輔助的柱子。

11 5.2 一個典型的遞迴範例：河內塔 〔說明〕 將1號金盤子從A搬到C 將2號金盤子從A搬到B，結果如下圖：

12 5.2 一個典型的遞迴範例：河內塔 〔說明〕 將1號金盤子由C搬到B 將2號金盤子由A搬到C，結果如下圖：

13 5.2 一個典型的遞迴範例：河內塔 〔說明〕 將1號金盤子由B搬到A 將2號金盤子由B搬到C，結果如下圖：

14 5.2 一個典型的遞迴範例：河內塔 〔說明〕 將1號金盤子由A搬到C，結果如下圖： 完成了！

15 5.2 一個典型的遞迴範例：河內塔 程式的追蹤如右：

16 5.3 另一個範例：八個皇后 這個遊戲的規則是，皇后之間不可在同一列（row）、同一行（column），也不可以在同一個對角線（diagonal）上，在這前提下，您是否可以為這些皇后們分派適當的位置，讓他們能和平相處。

17 5.3 另一個範例：八個皇后 八個皇后(eight queens)的問題，除了牽涉到遞迴，還包含了往回追蹤（Backtracking）的問題，何謂往回追蹤？其意義乃是當某一皇后無適當位置可放時，此時必須往回調整前一皇后的位置，以此類推，我們以四個皇后為例，如下情形：

18 5.3 另一個範例：八個皇后 此時第三個皇后沒有適當位置可放，因此必須移動第二個皇后，讓她在後一個位置，如

19 5.3 另一個範例：八個皇后 此時第三個皇后便可放在第三列的第二行。如

20 5.3 另一個範例：八個皇后

21 5.3 另一個範例：八個皇后 四個皇后最後的圖形如下： 上面的樹狀圖解釋如下：

22 5.3 另一個範例：八個皇后

23 5-4 何時不要使用遞迴？ 遞迴雖然可以使用少數幾行的敘述就可解決一複雜的問題，但有些問題會導致花更多的時間。
5-4 何時不要使用遞迴？ 遞迴雖然可以使用少數幾行的敘述就可解決一複雜的問題，但有些問題會導致花更多的時間。 費氏數列（Fibonacci number）的計算方式，某一數乃是前二位數的和，如 F0=1, F1=1, F2=F1+F0=2

24 5-4 何時不要使用遞迴？ 餘此類推 Fn=Fn-1+Fn-2對n≧2而言 以遞迴處理時，其遞迴樹（recursive tree）如下

25 5-4 何時不要使用遞迴？

26 5-4 何時不要使用遞迴？ 從上圖得知，F4、F3、F2、F1重覆執行多次，像這種遞迴樹重覆的動作太多，在此情況下，不適合用遞迴的。
5-4 何時不要使用遞迴？ 從上圖得知，F4、F3、F2、F1重覆執行多次，像這種遞迴樹重覆的動作太多，在此情況下，不適合用遞迴的。 此處可證明Fn其時間的複雜度是2n/2指數型態（exponential）。

27 5-4 何時不要使用遞迴？ 若以非遞迴，即以反覆式（iterative）程式執行，其程式請參閱5-1節中利用迴圈法（也可以說反覆式方法）計算費氏數列的Fibonacci函數。 從此片段程式中可以容易地看出其Big-O為O(n) 。

28 5-4 何時不要使用遞迴？

29 5-4 何時不要使用遞迴？ 從右邊往下做，直到1之後，再往上面做上去，這種遞迴樹不像一棵灌木（長得很強壯，不是瘦高型），而是一種簡單的鏈型（chain）型式。

30 5-4 何時不要使用遞迴？ 這種情形也不太適合用遞迴，而以非遞迴的方式處理較合適，分析如下：

31 5-4 何時不要使用遞迴？ 由於非遞迴使用了較多的區域變數（local variable），所以直覺上以為遞迴會較好，其實不然，因為遞迴使用了更多的時間存放暫時的結果，所以實際上遞迴花了更多的時間，因此，類似此種遞迴樹相當簡單，有如一條通道的，建議您還是使用非遞迴較佳。