遞歸算法的教學(xué)心得

才讓扎西

摘要：遞歸算法的主要作用是把復(fù)雜問題分解為簡單問題來求解。對(duì)于某些復(fù)雜問題（例如hanio塔問題），遞歸算法是一種自然且合乎邏輯的解決問題的方式，但是遞歸算法的執(zhí)行效率通常比較差。因此，在求解某些問題時(shí)，常采用遞歸算法來分析問題，用非遞歸算法來求解問題；另外，有些程序設(shè)計(jì)語言不支持遞歸，這就需要把遞歸算法轉(zhuǎn)換為非遞歸算法。

關(guān)鍵詞：遞歸；漢諾塔

中圖分類號(hào)：TP312 文獻(xiàn)標(biāo)識(shí)碼：A 文章編號(hào)：1009-3044（2013）08-1824-02

1 問題提出

在數(shù)據(jù)結(jié)構(gòu)教學(xué)中，常常聽到學(xué)生說C語言不好學(xué)，VC更不好學(xué)，而數(shù)據(jù)結(jié)構(gòu)是最最難學(xué)的一門課。其實(shí)這幾門課并不是什么難得讓人無法搞懂的課，只要有好的學(xué)習(xí)方法和多做實(shí)驗(yàn)，就很容易得手。學(xué)生們感到數(shù)據(jù)結(jié)構(gòu)難是因?yàn)樗乃惴ㄋ枷氡容^抽象，不好理解。下面以遞歸算法的教學(xué)為例，來談?wù)剶?shù)據(jù)結(jié)構(gòu)教學(xué)中的一些問題。

2 什么是遞歸

遞歸就是函數(shù)對(duì)于自身的直接或者間接調(diào)用，就像是在電視機(jī)屏幕里看到自己的影像，在畫面里有包含了一臺(tái)電視機(jī)，在那臺(tái)電視機(jī)屏幕里有包含所有眼前看到的畫面，當(dāng)然里面就會(huì)又有一個(gè)自己和一臺(tái)更小的電視機(jī)。如此循環(huán)往復(fù)，在更小的一臺(tái)電視機(jī)畫面里還會(huì)有更小的一幅畫面，在理論上這樣的循環(huán)式?jīng)]有終止的。這很像是遞歸算法的執(zhí)行過程，但有不同于遞歸，因?yàn)檫f歸算法需要一個(gè)終值，就是說它不允許循環(huán)無限制地進(jìn)行下去，要有一個(gè)返回的終值。一個(gè)函數(shù)在其定義中直接或間接調(diào)用自身的方法，通常能把一個(gè)大型的復(fù)雜的問題轉(zhuǎn)化為一個(gè)與原問題相似的規(guī)模較小的問題來解決，可以極大的減少程序代碼量。遞歸的能力在于用有限的語句來定義對(duì)象的無限集合。

所以，在書寫遞歸算法的時(shí)候要把好兩個(gè)關(guān)：

第一，遞歸就是函數(shù)或過程對(duì)于自身的直接或間接的調(diào)用，其標(biāo)志就是在調(diào)用時(shí)需要出現(xiàn)函數(shù)的名稱。也就是說，函數(shù)式通過名稱來調(diào)用自身的；

第二，在遞歸算法里，必須有一個(gè)明確的遞歸結(jié)束條件，也就是遞歸的出口，或者叫做參數(shù)需要一個(gè)終值，這個(gè)終值是遞歸開始返回的開關(guān)。

遞歸算法的執(zhí)行過程會(huì)有兩個(gè)階段：

第一個(gè)階段是遞推，就是把復(fù)雜的問題的求解推到比原問題簡單一些的問題的過程，其實(shí)這個(gè)過程可以叫做是遞歸調(diào)用的上段，是函數(shù)的調(diào)用過程；

第二個(gè)階段叫做回歸，也就是當(dāng)函數(shù)調(diào)用時(shí)的參數(shù)遇到了終值時(shí)，函數(shù)調(diào)用結(jié)束，函數(shù)可以地道一個(gè)明確的返回值，然后從這個(gè)返回開始，函數(shù)層層返回，依次給上一層調(diào)用返回一個(gè)明確的值，最終復(fù)雜的問題會(huì)得到一個(gè)最終解。

3 教學(xué)實(shí)例

數(shù)據(jù)結(jié)構(gòu)到底在學(xué)些什么？歸納一下我們學(xué)習(xí)的內(nèi)容，其實(shí)學(xué)到現(xiàn)在我們也就學(xué)了幾種普通的數(shù)據(jù)結(jié)構(gòu)，象二叉樹，樹，圖，還有排序的問題，前面的線性表和字符串也就是一些概念，當(dāng)然還有一個(gè)很重要的KMP算法，然后在每種數(shù)據(jù)結(jié)構(gòu)中我們也就是學(xué)到了若干處理的算法，我想真正數(shù)起來也就是幾十個(gè)算法吧。學(xué)習(xí)數(shù)據(jù)結(jié)構(gòu)也就是要掌握這幾十種算法，多簡單。至于如何掌握每個(gè)算法呢，我想就是多看看書，重要的是能夠理解。

4 結(jié)束語

通過這個(gè)實(shí)例，我們可以看出，遞歸算法書寫簡單，代碼很少。但是將遞歸算法非遞歸化，可以節(jié)省存儲(chǔ)空間，而且算法的執(zhí)行效率也有很大的提高。但是，究竟哪種算法更優(yōu)一些，這要看實(shí)際的問題求解過程。某種算法是可行的，但不一定就是最佳的。在一定的問題域里看似最佳的算法，當(dāng)參數(shù)出現(xiàn)變化時(shí)，又會(huì)出現(xiàn)許多問題。所以，算法教學(xué)首要的是教會(huì)學(xué)生一種思想，不是固定不變的程式。好的思想和靈活的編程技術(shù)相結(jié)合，是我們算法教學(xué)的最終目的。

參考文獻(xiàn)：

[1] 嚴(yán)蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)[M].北京： 清華大學(xué)出版社，1996.

[2] 李春葆.數(shù)據(jù)結(jié)構(gòu)析題與解析[M].北京： 清華大學(xué)出版社，1999.

[3] 蔣建初.高階擬線性時(shí)滯差分方程非振動(dòng)解的存在性與漸近性[J].婁底師專學(xué)報(bào)，2000（4）：41-46.

[4] Cheng S S， Patu W T. An existence theorem for a a nonlinear d ifference equ at ion[J]. Non linear Ana.l TMA20， 1993：193- 203.