Chapter 5 遞迴 資料結構導論 - C語言實作.

Presentation on theme: "Chapter 5 遞迴 資料結構導論 - C語言實作."— Presentation transcript:

1 Chapter 5 遞迴 資料結構導論 - C語言實作

2 5.1 前言 程式模組化 副程式(或函數(式)(Function))
某一處理程序，在處理的過程中又反覆地執行該處理程序，我們稱這種現象為遞迴(Recursive)。 如果撰寫程式來實作上述處理程序，將程式包裝成一支獨立的函數，該函數便可以反覆地自己呼叫自己，因此我們稱這個函數為遞迴函數。 資料結構導論 - C語言實作

3 5.2 遞迴函數的運作原理 計算2的5次方 25 = 2  = 2  (2  23) = 2  2  (2  22) = 2  2  2  (2  21) 2n = 2  2n-1，2n-1 = 2  2n-2 資料結構導論 - C語言實作

4 5.2 遞迴函數的運作原理 撰寫一個計算2的n次方的遞迴函數(式)程式，則該函數(式)將具備兩個主要特徵：
該遞迴函數(式)可以自己反覆地呼叫自己 第一次呼叫時的引數為n， 第二次呼叫時的引數為n-1， 第三次呼叫時的引數為n-2，...， 引數逐次遞減。 當引數值等於1時，必須停止遞迴呼叫。 資料結構導論 - C語言實作

5 用下列C語言程式來實作 long two_power_n(long n) { if(n == 0) return 1; if(n == 1)
return (2 * two_power_n(n-1)); else printf("\n錯誤! n 必須為正整數!\n"); } 資料結構導論 - C語言實作

6 5.2 遞迴函數的運作原理 資料結構導論 - C語言實作

7 5.3 撰寫遞迴函數程式的訣竅 撰寫遞迴函數程式的訣竅如下： 為遞迴函數取一個響亮的名稱？
思考遞迴函數須要哪些引數？及每一個引數的資料型態？ 遞迴函數自己呼叫自己時要帶入的參數值為何？ 遞迴函數的回傳值為何？如何在回傳時呼叫自己？ 遞迴函數的終止條件為何？終止遞迴時的回傳值為何？ 資料結構導論 - C語言實作

8 5.3 撰寫遞迴函數程式的訣竅 資料結構導論 - C語言實作

9 5.4 遞迴的應用 5.4.1 計算n階乘(n!) 5.4.2 列印費氏數列 5.4.3 列印河內塔的圓盤搬移過程
5.4.4 求兩個正整數的最大公因數 5.4.5 列出n筆不同資料所有可能的排列方式 資料結構導論 - C語言實作

10 5.4.1 計算n階乘(n!) 資料結構導論 - C語言實作

11 5.4.1 計算n階乘(n!) 資料結構導論 - C語言實作

12 5.4.1 計算n階乘(n!) 資料結構導論 - C語言實作

13 5.4.2 列印費氏數列 資料結構導論 - C語言實作

14 5.4.2 列印費氏數列 資料結構導論 - C語言實作

15 河內塔(Towers of Hanoi) 資料結構導論 - C語言實作

16 5.4.3 列印河內塔的圓盤搬移過程 資料結構導論 - C語言實作