楊新宇 蘭全祥
摘要:函數(shù)以及函數(shù)的遞歸調(diào)用是學(xué)習(xí)C語言必須要掌握的內(nèi)容,且遞歸作為經(jīng)典的算法思想被廣泛應(yīng)用于程序設(shè)計(jì)中。從應(yīng)用場景的角度出發(fā),對C語言中遞歸的定義、特征以及適用場景進(jìn)行了探討,并對這些適用場景進(jìn)行分析和舉例。最后,分析并探討了遞歸的優(yōu)缺點(diǎn),并給出了遞歸的優(yōu)化方法和將遞歸轉(zhuǎn)換為非遞歸的方法。
關(guān)鍵詞:C語言;遞歸;應(yīng)用;非遞歸化
中圖分類號:TP311 文獻(xiàn)標(biāo)識碼:A
文章編號:1009-3044(2020)22-0237-02
開放科學(xué)(資源服務(wù))標(biāo)識碼(0SID):
1 背景
隨著時(shí)代的進(jìn)步以及計(jì)算機(jī)編程語言的不斷發(fā)展,從20世紀(jì)80年代傳承至今的C語言始終是各大高校首選的計(jì)算機(jī)編程語言。世界編程語言排行榜( TIOBE)中C語言的熱門程度自2002年至今始終穩(wěn)居前三[1]。由此可見,C語言的重要程度以及熱門度。另外,模塊化設(shè)計(jì)是所有程序設(shè)計(jì)必須遵循的設(shè)計(jì)原則,而函數(shù)就是C語言模塊化的重要組成部分[2]。C語言函數(shù)以及函數(shù)的使用是學(xué)習(xí)C語言必須要掌握的內(nèi)容。遞歸作為經(jīng)典的函數(shù)使用方法,應(yīng)用范圍廣泛,是函數(shù)中不可或缺的重要內(nèi)容,也是作為一個(gè)開發(fā)者應(yīng)該掌握的重要算法之一。
2 遞歸的概述
2.1 定義
張長海等人認(rèn)為在定義一個(gè)函數(shù)時(shí),若在定義函數(shù)的內(nèi)部又出現(xiàn)對函數(shù)本身的調(diào)用,則稱該函數(shù)是遞歸的或遞歸定義的[3];譚浩強(qiáng)等人認(rèn)為遞歸就是函數(shù)自己直接或間接地調(diào)用自身的過程[4];丁雪晶認(rèn)為遞歸就是把要解決的問題分解成與原問題有相同解法,且規(guī)模較小的問題,直到遇見終止條件[5]。綜上,筆者認(rèn)為函數(shù)的遞歸就是直接或間接地調(diào)用自身進(jìn)行人棧操作,遇到邊界之后再進(jìn)行出棧的過程,且在人棧過程中,由原始問題分解為的子問題始終向邊界靠攏。
2.2 特征
從上述定義可得出遞歸的以下特征:
1)函數(shù)總是直接或者間接的調(diào)用自身;
2)函數(shù)的遞歸必須有結(jié)束條件(即問題的邊界),且在調(diào)用的過程中始終向某一個(gè)邊界靠近;
3)遞歸過程是一個(gè)不斷人棧和出棧的過程。
2.3 應(yīng)用場景
遞歸的本質(zhì)是將關(guān)于n的問題轉(zhuǎn)化為同類解法的關(guān)于m的問題,其中n和m是問題的規(guī)模,且m比n更靠近問題的邊界(遞歸結(jié)束條件)。
通過對常見遞歸應(yīng)用的分析,筆者將遞歸應(yīng)用場景分為三類:
1)數(shù)據(jù)的初始化是遞歸的。
2)數(shù)據(jù)的結(jié)構(gòu)是遞歸的。
3)問題的求解是遞歸的。
3 遞歸的案例
根據(jù)上述對函數(shù)遞歸的定義、特征以及應(yīng)用場景的總結(jié),本文對上述遞歸的應(yīng)用場景進(jìn)行分析和舉例。
3.1 數(shù)據(jù)的初始化是遞歸的
示例:Fibonacci數(shù)列(兔子數(shù)列)
描述:形如1,1,2,3,5,8,13,21I.….的數(shù)列被稱為Fibonac-Cl數(shù)列,即第n個(gè)數(shù)等于第n-l個(gè)數(shù)和第n-2個(gè)數(shù)之和。
分析:根據(jù)上述定義,對數(shù)列進(jìn)行數(shù)學(xué)歸納可得出數(shù)學(xué)遞推公式。
根據(jù)分析可知,F(xiàn)ibonacci數(shù)列是典型的數(shù)據(jù)的初始化是遞歸的例子,即要對n進(jìn)行初始化,必須知道n-l和n-2的值。
初始化Fibonacci數(shù)列的關(guān)鍵代碼如下:
int Fib(int n){
if(n ==1¨n==2){return 1;)
elsef
return Fib(n-I)+Fib(n-2);
)
)
3.2 數(shù)據(jù)的結(jié)構(gòu)是遞歸的
示例:二叉樹
描述:二叉樹是結(jié)點(diǎn)的有限集合,該集合或者為空集,或者是由一個(gè)根和兩棵互不相交的稱為該根的左子樹和右子樹的二叉樹組成[6]。
分析:由定義可知,一個(gè)根結(jié)點(diǎn)可能存在左子樹和右子樹,且左子樹和右子樹又是一顆更小的二叉樹。
因此,二叉樹從數(shù)據(jù)結(jié)構(gòu)上來看是遞歸的,如圖1所示,A的左子樹、A的右子樹以及C的左子樹都是一顆二叉樹,且無論是二叉樹的初始化還是遍歷都能用遞歸來解決。
構(gòu)造二叉樹的關(guān)鍵代碼如下:
typedef struct BiTNode{char data; struct BiTNode,*rchild,*rchild;}BiTNode,a:BiTree;
void CreateBiTree(BiTiree *T){
char c;scanf(”%c”,&c);
i“c==7#7){*T=NULL;】
elsef
*T= (BiTNode*)new BiTNode;
(*T)->data=c;
CreateBiTree(&(*T)->lchild);
CreateBiTree(&(*T)->rchild);
)
】
由代碼可以看出,在二叉樹的構(gòu)造中,輸入根節(jié)點(diǎn)數(shù)據(jù)之后還需要遞歸調(diào)用CreateBiTree函數(shù)對其左右子樹進(jìn)行構(gòu)造,即要成功構(gòu)造一顆二叉樹,需要先構(gòu)造出其左、右子樹。另外,二叉樹的遍歷也可采用遞歸的方法實(shí)現(xiàn)先序遍歷、中序遍歷與后序遍歷。
3.3 問題的求解是遞歸的
示例:漢諾塔
描述:現(xiàn)有A,B,C三根柱子,在A柱有n個(gè)從上到下面積依次增大的盤子,現(xiàn)在想把A柱這n個(gè)盤子移動(dòng)到C柱,但規(guī)定每一次只能移動(dòng)一個(gè)盤子,且三根柱子的盤子始終都保持著面積大的盤子在下,面積小的盤子在上,問盤子移動(dòng)的步驟。