C語言中遞歸函數的教學方法
導語:函數遞歸基於分治法思想,將複雜的大規模問題轉化爲小規模問題進行求解,在算法設計中具有重要的理論意義和實用價值,是C語言教學的難點。下面就由小編爲大家介紹一下C語言中遞歸函數的教學方法,歡迎大家閱讀!
1.引言
C語言是一種語法簡潔緊湊、運算符豐富、可移植性強、目標程序執行效率高的強數據類型語言,近年來在國內得到迅速的推廣應用。作爲我校信息類本科教學的入門語言,C語言是彙編語言、計算機原理、單片機程序設計等其他後繼課程的基礎,對整個教學過程具有重要的作用。
所有的C語言程序都由函數組成。在函數的調用中,直接或間接地調用自身的函數稱爲遞歸函數,相應的算法稱爲遞歸算法。在計算機算法設計與分析中,遞歸算法是一類較重要的算法,遞歸的使用往往使函數的定義和算法的描述簡潔且易於理解。
2.遞歸的基本原理
對於任何可以用計算機求解的問題,其求解難度與計算時間都與問題的規模有關。若一個規模較大的且難以直接解決的問題能夠分解爲k個規模較小的子問題,並且這些子問題互相獨立且與原問題相同,那麼可以通過對這些子問題進行分別求解,然後將各個子問題的解合併,得到原問題的解。其中P代表原始問題,P1、P2…Pk是比原始問題的規模|P|更小的子問題,Merge函數將子問題的解y1、y2…yk進行合併。
假設原始問題規模爲n,子問題P1、P2…Pk的規模爲n/m,分解閾值n0=1,且AdHoc函數求解規模爲1的問題耗費1個單位時間。再設合併函數Merge的時間複雜度爲f此時遞歸算法具有多項式的計算複雜度,其階數由子問題的`劃分數目k和子問題的規模n/m共同決定。
3.教學實例分析
函數的遞歸是C語言教學中的一個難點,本節根據上面給出的遞歸程序結構,通過一組從簡單到複雜的實例,逐步引導學生掌握遞歸程序編寫的技巧。
實例1(階乘問題):計算整數n的階乘。
分析:該問題可使用下述遞歸結構進行求解:
(1)當n=1時,可以直接計算n!=1;
(2)當n>1時,n!可以通過對1個小規模的子問題(n-1)!的求解得到,也即n!=(n-1)!*n。
實例2(Hanoi塔問題):設a、b、c是三個塔座。開始時,在a座處自上而下、從小到大地疊放n個圓盤,編號分別爲1、2、…n,如圖1所示。現要求將a座處的所有圓盤按同樣的次序堆疊到b座上,並且要求:(1)每次只能移動1個圓盤;(2)任何時候都不允許將大盤壓在小盤的上方。
分析:該問題可使用下述遞歸結構進行求解:
(1)當n=1時,直接將盤從a座移動到b座;
(2)當n>1時,將圓盤按下列方法移動(見圖2):
①將a座上的n-1個盤移動到c座;
②將a座的第n個盤移動到b座;
③將c座上的n-1個盤移動到b座。
根據以上分析,可以寫出如下的程序:
實例3(排序問題):對n個元素的整型數組array進行排序。
分析:該問題可使用下述遞歸結構進行求解:
(1)當n=1時,直接輸出排序結果;
(2)當n>1時,按下列方法進行排序:
①將array分成大小基本相同的兩部分;
②對兩個子數組分別進行排序;
③將兩個排序後的子數組進行合併。
其中參數left和right分別代表當前數組的第1個元素和最後一個元素的下標。
對於該排序算法,子問題的數目k=2,規模n/m = n/2。因爲函數Merge的合併操作可以在線性時間內完成,所以由(3)式可以得到相應的時間複雜度爲
T(n)=O(nlogn)(4)
4.結語
在C語言教學中,函數的遞歸一直是教學的重點和難點。本文首先從理論上給出遞歸的程序結構,然後以該結構爲指導,通過一組程序實例,引導學生掌握遞歸程序的編寫技巧,理解應用分治法解決複雜問題的思想。實踐證明,本方法在課堂教學中取得較好的效果。
相關文章
-
C語言函數遞歸教程
引導語:遞歸做爲一種算法在程序設計語言中廣泛應用。以下是本站小編分享給大家的C語言函數遞歸教程,歡迎閱讀!一、棧在說函數遞歸的時候,順便說一下棧的概念。棧是一個後進先出的壓入(push)和彈出(pop)式數據結構。在程 -
C語言函數的遞歸調用
分分鐘搞定的早餐一定是最吸引人的,因爲你無需犧牲睡眠時間。好吃又營養的早餐餅,走一個.......主要材料:雞蛋 2個牛奶 250克麪粉 150克細砂糖 20克所需工具:不粘平底鍋攪拌桶硅膠刮刀製作步驟:第1步:麪粉篩兩遍,雞 -
C語言函數的遞歸和調用
C語言中的函數可以遞歸調用,即:可以直接(簡單遞歸)或間接(間接遞歸)地自己調自己。下面是小編爲大家整理的C語言函數的遞歸和調用,歡迎參考~ 一、要點:1、C語言函數可以遞歸調用。2、可以通過直接或間接兩種方式調用。 -
關於C語言函數的遞歸和調用
C語言中的函數可以遞歸調用,即:可以直接(簡單遞歸)或間接(間接遞歸)地自己調自己。下面本站小編帶大家一起來看看詳細內容,需要的朋友可以參考一下!想了解更多相關信息請持續關注我們應屆畢業生考試網! 一、要點:1、C -
C語言遞歸函數的執行與求解
導語:函數的遞歸調用是在調用一個函數的執行過程中,直接或間接地調用該函數本身,使用遞歸函數的程序結構清晰,簡單、易懂。下面就由小編爲大家介紹一下C語言遞歸函數的執行與求解,歡迎大家閱讀! 1 遞歸函數C語言的特點 -
C語言中函數之間地址傳遞方式
導語:C語言中函數之間的數據傳遞方式有值傳遞、引用傳遞、地址傳遞。下面就由小編爲大家介紹一下C語言中函數之間地址傳遞方式,歡迎大家閱讀! 1 函數之間數據傳遞方式分類C語言程序是由函數組成的。設計C語言程序時, -
C語言函數教學方法
導語:針對C語言中函數的重要性及我校學生在學習過程中對函數的掌握情況,總結出一套實用的c語言函數教學方法。下面就由小編爲大家介紹一下C語言函數教學方法,歡迎大家閱讀! 1序言《C程序設計基礎》是我校工科非計算機 -
C語言中遞歸算法的剖析
C通過運行時堆棧支持遞歸函數的實現。遞歸函數就是直接或間接調用自身的函數。以下是小編爲大家搜索整理的對C語言中遞歸算法的剖析,希望能給大家帶來幫助!更多精彩內容請及時關注我們應屆畢業生考試網!這裏有一個簡單 -
深入解釋c語言中的遞歸算法
引導語:遞歸函數是直接或間接調用自身的函數。以下是本站小編分享給大家的深入解釋c語言中的遞歸算法,歡迎閱讀!這裏有一個簡單的程序,可用於說明遞歸。程序的目的是把一個整數從二進制形式轉換爲可打印的字符形式。例如 -
對C語言中遞歸算法的深入解析
C通過運行時堆棧支持遞歸函數的實現。遞歸函數就是直接或間接調用自身的函數。下面是小編爲大家帶來的對C語言中遞歸算法的深入解析,歡迎閱讀。 對C語言中遞歸算法的深入解析許多教科書都把計算機階乘和菲波那契數