C語言函數的遞歸調用

秦玉平，冷強奎，馬靖善

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

0 引言

遞歸是一種重要且應用廣泛的程序設計方法[1-4]．使用遞歸既便于程序的編寫和調試，又能使程序結構簡潔清晰、可讀性好[5]．

在C語言中，函數是構成C程序的基本單位，函數可以遞歸調用，即在一個函數的函數體中可以直接或間接地調用該函數本身，這個函數稱為遞歸函數．

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

1 遞歸函數定義

根據調用方式，遞歸調用分為直接遞歸和間接遞歸兩種．

直接遞歸函數定義的一般形式為：

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

{

┇

函數名(實際參數表)；

┇

}

間接遞歸函數定義的一般形式為：

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

{

┇

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

┇

}

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

{

┇

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

┇

}

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

long F(int n)

{long s；

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

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

return s；

}

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

long F(int n)

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

else return n*G(n-1)； /*函數F調用函數G*/

}

long G(int n)

{return F(n)；} /*函數G調用函數F*/

2 遞歸調用條件

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

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

F(S0)=C0

(1)

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

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

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

(2)

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

例如，例1的數學模型為：

(3)

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

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

3 遞歸函數設計

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

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

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

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

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

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

(4)

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

long Fib(int n)

{long f；

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

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

return f； /*返回結果*/

}

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

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

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

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

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

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

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

上述操作步驟對應的C語言函數描述如下．

typedef char ElemType； /*結點數據域類型，假設為字符型*/

typedef struct node

{ElemType data； /*數據域*/

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

}BitTree； /*結點類型*/

void PreOrder(BitTree*bt)

{if(bt!=NULL)

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

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

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

}

}

4 遞歸調用執行過程

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

圖1 遞歸調用過程

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

圖2 遞歸調用求解過程

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

5 遞歸轉換為非遞歸

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

(1)中間變量法

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

設置變量

while(沒到原問題規模)

{求解當前規模問題

擴大問題規模

}

一般地，為函數的每一個形參設置一個局部變量．另外，根據求解關系設置一些存放中間結果的變量．

【例5】將例3轉換成非遞歸．

long Fib(int n)

{long i=3； /*設置形參對應的變量*/

int f1=1，f2=1，temp； /*設置存放之間結果的變量*/

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

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

i++； /*修改形參對應變量值*/

}

return f2；

}

(2)工作棧法

轉換方法是先設置用于保存現場信息的工作棧，然后用循環模擬遞歸求解過程．其一般過程如下：

設置棧并初始化

原問題現場信息壓棧

while(棧非空)

{彈棧

處理有解子問題

未求解子問題現場信息壓棧

}

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

【例6】將例4轉換成非遞歸．

#define MAXSIZE 20 /*設置棧長，假設為20*/

void PreOrder(BitTree*bt)

{BitTree*stack[MAXSIZE]，*p=bt； /*設置棧和形參對應的變量*/

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

if(bt!=NULL)

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

while(top>0)

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

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

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

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

}

}

}

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

void PreOrder1(BitTree*bt)

{BitTree*stack[MAXSIZE]，*p=bt； /*設置棧和形參對應的變量*/

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

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

while(top>0)

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

while(p)

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

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

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

}

}

}

6 結束語

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