Chapter 5 遞迴 資料結構導論 - C語言實作
5.1 前言 程式模組化 副程式(或函數(式)(Function)) 某一處理程序，在處理的過程中又反覆地執行該處理程序，我們稱這種現象為遞迴(Recursive)。 如果撰寫程式來實作上述處理程序，將程式包裝成一支獨立的函數，該函數便可以反覆地自己呼叫自己，因此我們稱這個函數為遞迴函數。 資料結構導論 - C語言實作
5.2 遞迴函數的運作原理 計算2的5次方 25 = 2 24 = 2 (2 23) = 2 2 (2 22) = 2 2 2 (2 21) 2n = 2 2n-1，2n-1 = 2 2n-2 資料結構導論 - C語言實作
5.2 遞迴函數的運作原理 撰寫一個計算2的n次方的遞迴函數(式)程式，則該函數(式)將具備兩個主要特徵： 該遞迴函數(式)可以自己反覆地呼叫自己 第一次呼叫時的引數為n， 第二次呼叫時的引數為n-1， 第三次呼叫時的引數為n-2，...， 引數逐次遞減。 當引數值等於1時，必須停止遞迴呼叫。 資料結構導論 - C語言實作
用下列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語言實作
5.2 遞迴函數的運作原理 資料結構導論 - C語言實作
5.3 撰寫遞迴函數程式的訣竅 撰寫遞迴函數程式的訣竅如下： 為遞迴函數取一個響亮的名稱？ 思考遞迴函數須要哪些引數？及每一個引數的資料型態？ 遞迴函數自己呼叫自己時要帶入的參數值為何？ 遞迴函數的回傳值為何？如何在回傳時呼叫自己？ 遞迴函數的終止條件為何？終止遞迴時的回傳值為何？ 資料結構導論 - C語言實作
5.3 撰寫遞迴函數程式的訣竅 資料結構導論 - C語言實作
5.4 遞迴的應用 5.4.1 計算n階乘(n!) 5.4.2 列印費氏數列 5.4.3 列印河內塔的圓盤搬移過程 5.4.4 求兩個正整數的最大公因數 5.4.5 列出n筆不同資料所有可能的排列方式 資料結構導論 - C語言實作
5.4.1 計算n階乘(n!) 資料結構導論 - C語言實作
5.4.1 計算n階乘(n!) 資料結構導論 - C語言實作
5.4.1 計算n階乘(n!) 資料結構導論 - C語言實作
5.4.2 列印費氏數列 資料結構導論 - C語言實作
5.4.2 列印費氏數列 資料結構導論 - C語言實作
河內塔(Towers of Hanoi) 資料結構導論 - C語言實作
5.4.3 列印河內塔的圓盤搬移過程 資料結構導論 - C語言實作