Download presentation
Presentation is loading. Please wait.
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語言實作
Similar presentations