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

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

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

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

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

5.1 一些遞迴的基本範例

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

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

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

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

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

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

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

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

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

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

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

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

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

5.3 另一個範例：八個皇后

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

5.3 另一個範例：八個皇后

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

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

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

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

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

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

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

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

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