摘要：本文從實際教學(xué)出發(fā)，首先討論了遞歸的基本條件，總結(jié)出遞歸程序的設(shè)計方法，然后詳細分析遞歸程序的執(zhí)行過程并給出了遞歸程序的一般結(jié)構(gòu)，最后讓學(xué)生自己分析漢諾塔問題并動手寫程序，在教學(xué)中取得了較好的效果。

關(guān)鍵詞：函數(shù)；遞歸；教學(xué)

中圖分類號：G642

文獻標(biāo)識碼：A

文章編號：1672-5913(2008)02-0057-02

1引言

C語言一般作為計算機及相關(guān)專業(yè)的第一門語言，它是后續(xù)計算機課程的基礎(chǔ)，學(xué)生對它的掌握程度直接影響到后續(xù)課程的學(xué)習(xí)。函數(shù)是C語言中一個非常重要的部分，所有程序都是由函數(shù)組成的，如果沒有掌握函數(shù)，就不可能掌握C語言。在函數(shù)中，遞歸函數(shù)是一類比較難以掌握的問題，學(xué)生在學(xué)習(xí)過程中往往對這類程序的執(zhí)行過程不了解，對遞歸問題的認識不清楚，難以寫出正確的遞歸程序。針對遞歸問題的教學(xué)，人們在實踐中做了很多有益的探討，也有一些教材對這一問題做了較為細致的分析。但以上工作大都以漢諾塔問題進行講解，而漢諾塔問題本身較為復(fù)雜，很多學(xué)生一下難以掌握該程序的執(zhí)行過程。本文從實際教學(xué)出發(fā)，首先分析遞歸的基本條件，從簡單程序開始分析，寫出遞歸程序，然后一步一步分析遞歸程序的執(zhí)行過程，讓學(xué)生對遞歸有更深入的理解。然后寫出遞歸程序的一般結(jié)構(gòu)，最后分析漢諾塔問題，讓學(xué)生自己寫出程序。

2遞歸的基本條件

一般情況下采用遞歸方法來解決問題，必須符合以下三個條件：

a. 可以把要解決的問題轉(zhuǎn)化為一個新問題，而這個新的問題的解決方法仍與原來的解決方法相同，只是所處理的問題的規(guī)模有規(guī)律地遞減。也就是說解決問題的方法相同，調(diào)用函數(shù)的參數(shù)每次不同(有規(guī)律地遞減)，如果沒有規(guī)律也就不能運用遞歸方法求解。

b. 每個子問題必須比原來問題的規(guī)模更小，即使小一號也行，如果能夠迅速減小規(guī)模更好。

c. 必定要有一個明確的結(jié)束遞歸的條件。當(dāng)問題的規(guī)模達到一定程度時(一般的時候應(yīng)該是規(guī)模足夠小)，問題的解是已知的，在這個地方能結(jié)束遞歸調(diào)用，不然可能導(dǎo)致系統(tǒng)崩潰或陷入死循環(huán)。

3遞歸問題分析

遞歸程序最少有兩種方法可以寫出。第一種是想辦法把問題轉(zhuǎn)化為數(shù)學(xué)表達式，能用數(shù)學(xué)表達式寫出的，可以直接把數(shù)學(xué)表達式變?yōu)槌绦?；第二種是按照遞歸的基本條件，分析所給問題的結(jié)構(gòu)，一個問題總具有一定的規(guī)模，想辦法把規(guī)模變小，使小規(guī)模的問題與原問題具有相同的解法，當(dāng)規(guī)模足夠小時，該問題的解是已知的，這時可以套用后面所講的一般遞歸程序的結(jié)構(gòu)來寫遞歸程序。

例1：求n！。經(jīng)過分析n！可以表示為

假定n！是一個long型，則直接寫出程序如下：

long func(int n) //求n！

{if(n==1 || n==0)

return 1;

return n*func(n-1);

}

例2：求Fibonacci數(shù)列(非波納契)的第n項，該數(shù)列表示如下：

按照例1的方法，寫出程序如下：

longfib(int n)

{ if( (n==1||(n==2) )

① return 1;

else

② return fib(n-1)+fib(n-2);

}

如輸入n＝4，程序(具體程序用行標(biāo)號代替)的執(zhí)行過程如圖1所示，通過分析以上程序，大部分學(xué)生對遞歸函數(shù)的執(zhí)行過程有了較為清晰的認識。

例3：用遞歸的方法將一個正整數(shù)n按位輸出，如輸入2008，輸出2 0 0 8，n的位數(shù)不確定，可以是任意正整數(shù)。

分析：

① 函數(shù)應(yīng)該是處理整數(shù)n，并且是輸出，用PrintNum(int n)來實現(xiàn)這一功能；

② 如果n的規(guī)模很小(只有1位)，可以直接輸出后結(jié)束程序；(這里應(yīng)該知道n的位數(shù)是問題的規(guī)模)

③ 把問題的規(guī)模變小，去掉n的某1位(在實際講解時是去掉個位，因為去掉個位比較容易一些，我們用k=n%10保存?zhèn)€位，n=n/10就可以去掉個位)，余下位形成一個新的規(guī)模比原數(shù)小的數(shù)，再在新數(shù)上遞歸調(diào)用函數(shù)，這個新數(shù)按要求輸出后，去掉的這一位因為是個位，所以應(yīng)該把它輸出到新數(shù)的后面。

通過以上分析，寫出程序如下：

void PrintNum(int n)/*該函數(shù)能把n按要求輸出*/

{ int k;

if(n<10){ printf(\"%2d\"，n); return ;} /*如果規(guī)模很小，則直接處理后結(jié)束程序*/

k=n%10; /*在n中提出個位數(shù)字*/

PrintNum(n/10);/*把規(guī)模更小的子問題遞歸調(diào)用函數(shù)來處理*/

printf(\"%2d\"，k);

}

通過以上三個例子，學(xué)生對遞歸函數(shù)有了較為清晰的認識，對遞歸程序的寫法有了一定的掌握之后，我們可以總結(jié)出一個一般遞歸程序的結(jié)構(gòu)如下，幾乎所有遞歸程序都可以按照這個結(jié)構(gòu)去分析并寫程序。

ReturnType Function(問題描述及規(guī)模)/* 在程序內(nèi)部我們應(yīng)該認為函數(shù)Function已經(jīng)具備處理這類問題的功能，它可以直接被調(diào)用 */

{ 當(dāng)規(guī)模足夠小的時候，直接給出結(jié)果(有可能什么都不做)，返回；

把原問題分解為規(guī)模更小一些的子問題，在這些子問題上遞歸調(diào)用函數(shù)，并注意所有子問題都被處理到。

}

我們根據(jù)這個結(jié)構(gòu)，要求學(xué)生回過來簡單看一下前面的三個例子，多數(shù)學(xué)生便會對遞歸有更為深入的認識。之后引入漢諾塔問題，該問題的分析方法類似于例3，并套用這個結(jié)構(gòu)，讓學(xué)生自己試著寫該問題的程序，可以發(fā)現(xiàn)有一部分學(xué)生能自己寫出遞歸函數(shù)來。

4總結(jié)

在C語言中，函數(shù)一直是學(xué)習(xí)的重點和難點，遞歸又是最難掌握的一類函數(shù)，本文從實際教學(xué)需要出發(fā)，首先分析遞歸的基本條件，從由易到難的順序，設(shè)計了一些教學(xué)實例，重點讓學(xué)生了解遞歸函數(shù)的寫法以及執(zhí)行情況，最后總結(jié)出遞歸函數(shù)的一般程序結(jié)構(gòu)，使學(xué)生能正確設(shè)計遞歸程序，在實際教學(xué)中取得了良好的效果。

A Discussion of the Teachin2g-Method of Recursion Function in C Language

Abstract: Recursion function is difficult in C language. Performance of this function and designing program are difficult for student. Setting out from the actual teaching， the article firstly discusses the basic condition for recursion function and concludes methods of designing recursion function， then analyses the performance of recursion function in detail and develops general structure of it， finally， make students analyze problem of Hanoi and design program. It produces a good effect.

Keywords: function， recursion， teaching

收稿日期：2007-10

作者簡介：

徐洪智(1974-)，男，湖南長沙人。吉首大學(xué)講師，碩士，高級程序員，研究方向為算法設(shè)計與分析，網(wǎng)格計算。

聯(lián)系地址：湖南 張家界 吉首大學(xué) 張家界校區(qū) 信息管理與工程學(xué)院 郵編427000

TEL：13974413996

E-mail：xuhongzhi9@163.com

張彬連(1978-)，女，湖南湘潭人。吉首大學(xué)講師，碩士，研究方向為計算機網(wǎng)絡(luò)。

注：“本文中所涉及到的圖表、注解、公式等內(nèi)容請以PDF格式閱讀原文。”