秦玉平，冷強奎，馬靖善

(1．渤海大學(xué) 數(shù)學(xué)科學(xué)學(xué)院，遼寧 錦州121013；2．遼寧工程技術(shù)大學(xué) 電子與信息工程學(xué)院，遼寧 葫蘆島125105；3．渤海大學(xué) 信息科學(xué)與技術(shù)學(xué)院，遼寧 錦州121013)

0 引言

遞歸是一種重要且應(yīng)用廣泛的程序設(shè)計方法[1-4]．使用遞歸既便于程序的編寫和調(diào)試，又能使程序結(jié)構(gòu)簡潔清晰、可讀性好[5]．

在C語言中，函數(shù)是構(gòu)成C程序的基本單位，函數(shù)可以遞歸調(diào)用，即在一個函數(shù)的函數(shù)體中可以直接或間接地調(diào)用該函數(shù)本身，這個函數(shù)稱為遞歸函數(shù)．

函數(shù)是C語言的重點，遞歸函數(shù)又是學(xué)習(xí)函數(shù)的難點．為便于學(xué)習(xí)者深入理解C語言中函數(shù)遞歸調(diào)用的運行機制，并熟練使用遞歸調(diào)用進行C語言程序設(shè)計，本文對C語言遞歸函數(shù)的定義、遞歸條件、遞歸函數(shù)設(shè)計、遞歸調(diào)用執(zhí)行過程以及遞歸轉(zhuǎn)換成非遞歸的方法都進行了詳細(xì)闡述，并通過實例進行了深入解析．

1 遞歸函數(shù)定義

根據(jù)調(diào)用方式，遞歸調(diào)用分為直接遞歸和間接遞歸兩種．

直接遞歸函數(shù)定義的一般形式為：

[存儲類別][返回值類型]函數(shù)名(形式參數(shù)表)

{

┇

函數(shù)名(實際參數(shù)表)；

┇

}

間接遞歸函數(shù)定義的一般形式為：

[存儲類別1][返回值類型1]函數(shù)名1(形式參數(shù)表1)

{

┇

函數(shù)名2(實際參數(shù)表2)；

┇

}

[存儲類別2][返回值類型2]函數(shù)名2(形式參數(shù)表2)

{

┇

函數(shù)名1(實際參數(shù)表1)；

┇

}

【例1】用直接遞歸計算n!．

long F(int n)

{long s；

if(n==0||n==1)s=1；

else s=n*F(n-1)； /*直接遞歸調(diào)用*/

return s；

}

【例2】用間接遞歸計算n!．

long F(int n)

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

else return n*G(n-1)； /*函數(shù)F調(diào)用函數(shù)G*/

}

long G(int n)

{return F(n)；} /*函數(shù)G調(diào)用函數(shù)F*/

2 遞歸調(diào)用條件

一般地，一個能用遞歸函數(shù)解決的問題須滿足兩個條件：一是該問題能夠縮小規(guī)模且縮小規(guī)模后的問題與原問題具有相同的求解方法，即能夠歸納出遞歸項，又稱遞歸體；二是須有遞歸結(jié)束的條件，又稱遞歸出口．具體而言，一個遞歸模型由遞歸項和遞歸結(jié)束條件兩部分組成．

遞歸結(jié)束條件確定遞歸到何時結(jié)束，其一般格式為：

F(S0)=C0

(1)

其中，S0和C0都是常量，C0表示問題規(guī)模為S0時的解，一些遞歸問題可能有多個遞歸出口．

遞歸項確定遞歸方式，其一般格式為：

F(S)=G(F(S1)，F(xiàn)(S2)，…，F(xiàn)(Sm)，C1，C2，…，Cn)

(2)

其中，S是原問題，S1、S2、……、Sm是與原問題解法相同的小問題，C1、C2、……、Cn表示能用非遞歸方法解決的問題．G是一個函數(shù)，表示遞歸問題的結(jié)構(gòu)．

例如，例1的數(shù)學(xué)模型為：

(3)

遞歸項為F(n)=n × F(n-1)，遞歸結(jié)束條件為F(0)=1和F(1)=1．

如果要解決的問題不是計算求值，而是完成指定的操作(如輸出等)，則其遞歸模型難以用數(shù)學(xué)表達(dá)式描述，此時可以用解決問題的操作步驟描述．

3 遞歸函數(shù)設(shè)計

用遞歸形式的函數(shù)解決實際問題時，首先要給出遞歸模型，即給出遞歸項和遞歸結(jié)束條件，然后用C語言函數(shù)描述遞歸模型．其中的關(guān)鍵是遞歸模型設(shè)計，具體步驟如下：

(1)對原問題F(S)進行分析，將其分解為小問題F(S1)、F(S2)、……、F(Sm)，并保證每個小問題的求解過程和環(huán)境都與原問題相似；

(2)假設(shè)每個小問題F(Si)(i=1，2，…，m)都是可解的，在此基礎(chǔ)上確定F(S)的解，即給出F(S)與F(S1)、F(S2)、……、F(Sm)之間的關(guān)系；

(3)確定特定情況的解，以此作為遞歸結(jié)束條件．

【例3】用遞歸法計算Fibonacci序列第n項的值．

Fibonacci序列第1項和第2項的值都是1，從第3項起每項的值是其前兩項的和．設(shè)第n項的值為F(n)，則將原問題F(n)分解為F(n-1)和F(n-2)，且F(n)與F(n-1)和F(n-2)的關(guān)系為F(n)=F(n-1)+F(n-2)，特定情況的解為F(1)=1和F(2)=1．由此可知，該問題的數(shù)學(xué)模型為：

(4)

遞歸模型式(3)的C語言函數(shù)描述如下．

long Fib(int n)

{long f；

if(n==1||n==2) f=1； /*遞歸出口*/

else f=Fib(n-1)+Fib(n-2)； /*遞歸項*/

return f； /*返回結(jié)果*/

}

【例4】先序遞歸遍歷二叉樹．

先序遞歸遍歷二叉樹的操作步驟如下．

若二叉樹為空，則遍歷結(jié)束，否則進行下列操作：

(1)訪問(輸出)根結(jié)點；

(2)先序遞歸遍歷根的左子樹；

(3)先序遞歸遍歷根的右子樹．

遞歸項為(1)～(3)三步，遞歸結(jié)束條件是二叉樹為空(NULL)．

上述操作步驟對應(yīng)的C語言函數(shù)描述如下．

typedef char ElemType； /*結(jié)點數(shù)據(jù)域類型，假設(shè)為字符型*/

typedef struct node

{ElemType data； /*數(shù)據(jù)域*/

struct node*lchild，*rchild； /*左右指針域*/

}BitTree； /*結(jié)點類型*/

void PreOrder(BitTree*bt)

{if(bt!=NULL)

{printf("%c"，bt->data)；

PreOrder(bt->lchild)； /*遞歸調(diào)用*/

PreOrder(bt->rchild)； /*遞歸調(diào)用*/

}

}

4 遞歸調(diào)用執(zhí)行過程

遞歸調(diào)用實質(zhì)上是嵌套調(diào)用的一種特殊情況，所不同的是遞歸調(diào)用的調(diào)用函數(shù)和被調(diào)用函數(shù)是同一個函數(shù)，每執(zhí)行一次調(diào)用就向遞歸結(jié)束條件靠近一步，當(dāng)遇到遞歸結(jié)束條件時再逐層返回．遞歸函數(shù)的執(zhí)行次數(shù)稱為遞歸的層數(shù)，又稱遞歸深度．第一次調(diào)用是由主調(diào)函數(shù)進入第一層，第i(1

圖1 遞歸調(diào)用過程

由圖1可以看出，遞歸調(diào)用的求解過程包括下推和回代兩個階段．下推階段是從原問題出發(fā)，逐漸縮小問題的規(guī)模，直到遞歸結(jié)束條件，最終實現(xiàn)從未知到已知．回代階段是從已知出發(fā)，按照下推的逆過程逐一求解，最終到達(dá)下推的開始處，完成對原問題求解．例如，用例1求4!的遞歸調(diào)用求解過程如圖2所示．

圖2 遞歸調(diào)用求解過程

在C語言中，函數(shù)調(diào)用開始，為自動型局部變量分配存儲單元，函數(shù)調(diào)用結(jié)束釋放[6-7]，并返回到調(diào)用函數(shù)的固定位置繼續(xù)執(zhí)行后面的語句．因此，在遞歸調(diào)用的下推階段需要保存自動型局部變量值和返回地址等現(xiàn)場信息，在回代階段需要恢復(fù)現(xiàn)場信息，這些現(xiàn)場信息的管理是通過系統(tǒng)工作棧來實現(xiàn)的．在遞歸函數(shù)開始運行時，系統(tǒng)先為遞歸函數(shù)建立一個系統(tǒng)工作棧．在每次遞歸調(diào)用開始前，系統(tǒng)自動將當(dāng)前層的自動型局部變量值和返回地址等現(xiàn)場信息壓棧；在每次遞歸調(diào)用結(jié)束后，又自動彈棧，把棧頂元素值分別賦給上一層相應(yīng)的局部變量，使它們都恢復(fù)到調(diào)用前的狀態(tài)，并將程序控制轉(zhuǎn)到返回地址指定的位置．

5 遞歸轉(zhuǎn)換為非遞歸

遞歸問題都可以轉(zhuǎn)換成非遞歸問題[8-10]．依據(jù)遞歸調(diào)用在函數(shù)中的位置，遞歸調(diào)用分為尾遞歸調(diào)用和非尾遞歸調(diào)用．這兩種遞歸在轉(zhuǎn)換成非遞歸時使用的方法不同．尾遞歸調(diào)用是指遞歸調(diào)用在函數(shù)的尾部，后面沒有要執(zhí)行的語句，其求解過程不進行回溯，轉(zhuǎn)換成非遞歸時使用工作變量保存現(xiàn)場信息，稱為中間變量法．非尾遞歸調(diào)用是指遞歸調(diào)用的后面還有要執(zhí)行的語句，其求解過程要進行回溯，轉(zhuǎn)換成非遞歸問題時使用工作棧保存現(xiàn)場信息，稱為工作棧法．

(1)中間變量法

轉(zhuǎn)換方法是先設(shè)置用于保存現(xiàn)場信息的變量，然后從遞歸出口開始，根據(jù)遞歸項依次求解規(guī)模較大的子問題，直至得到原問題的解．其一般過程如下：

設(shè)置變量

while(沒到原問題規(guī)模)

{求解當(dāng)前規(guī)模問題

擴大問題規(guī)模

}

一般地，為函數(shù)的每一個形參設(shè)置一個局部變量．另外，根據(jù)求解關(guān)系設(shè)置一些存放中間結(jié)果的變量．

【例5】將例3轉(zhuǎn)換成非遞歸．

long Fib(int n)

{long i=3； /*設(shè)置形參對應(yīng)的變量*/

int f1=1，f2=1，temp； /*設(shè)置存放之間結(jié)果的變量*/

while(i<=n) /*循環(huán)終止條件為i>n*/

{temp=f1+f2；f1=f2；f2=temp； /*求解子問題*/

i++； /*修改形參對應(yīng)變量值*/

}

return f2；

}

(2)工作棧法

轉(zhuǎn)換方法是先設(shè)置用于保存現(xiàn)場信息的工作棧，然后用循環(huán)模擬遞歸求解過程．其一般過程如下：

設(shè)置棧并初始化

原問題現(xiàn)場信息壓棧

while(棧非空)

{彈棧

處理有解子問題

未求解子問題現(xiàn)場信息壓棧

}

一般地，用一維數(shù)組表示順序棧，其類型與相應(yīng)的函數(shù)參數(shù)類型相同，棧長不小于遞歸的深度．

【例6】將例4轉(zhuǎn)換成非遞歸．

#define MAXSIZE 20 /*設(shè)置棧長，假設(shè)為20*/

void PreOrder(BitTree*bt)

{BitTree*stack[MAXSIZE]，*p=bt； /*設(shè)置棧和形參對應(yīng)的變量*/

int top=0； /*棧初始化*/

if(bt!=NULL)

{stack[top++]=p； /*根結(jié)點指針壓棧*/

while(top>0)

{p=stack[--top]； /*彈棧*/

printf("%4c"，p->data)； /*遍歷(輸出)*/

if(p->rchild) stack[top++]=p->rchild； /*右子樹根結(jié)點指針壓棧*/

if(p->lchild) stack[top++]=p->lchild； /*左子樹根結(jié)點指針壓棧*/

}

}

}

在將遞歸轉(zhuǎn)換成非遞歸時，可同時使用棧和變量保存現(xiàn)場信息．例如，將例4轉(zhuǎn)換成非遞歸時可用下面方法．此時用變量p保存左子樹根結(jié)點信息，用棧stack保存右子樹根結(jié)點信息．

void PreOrder1(BitTree*bt)

{BitTree*stack[MAXSIZE]，*p=bt； /*設(shè)置棧和形參對應(yīng)的變量*/

int top=0； /*棧初始化*/

stack[top++]=p； /*根結(jié)點指針壓棧*/

while(top>0)

{p=stack[--top]； /*彈棧*/

while(p)

{printf("%4c"，p->data)； /*遍歷(輸出)*/

if(p->rchild) stack[top++]=p->rchild； /*右子樹根結(jié)點指針壓棧*/

p=p->lchild； /*用變量保存左子樹根結(jié)點指針*/

}

}

}

6 結(jié)束語

用C語言求解具有遞歸特征的問題時，可采用遞歸函數(shù)來實現(xiàn)．遞歸函數(shù)設(shè)計的步驟是先找到求解問題的遞歸項和遞歸結(jié)束條件，然后用C語言函數(shù)描述．遞歸調(diào)用具程序結(jié)構(gòu)清晰、代碼量少、可讀性好等優(yōu)點．但它也有執(zhí)行效率低、占用內(nèi)存空間多等缺點．其原因是遞歸調(diào)用需要?？臻g保存現(xiàn)場信息，遞歸的層次越多，需要的存儲空間越多，壓棧和彈棧的時間開銷也越多．因此，在對執(zhí)行效率要求較高的情況下，需將其轉(zhuǎn)換成非遞歸方式．