程序設(shè)計中的遞歸與棧

摘 要：在程序設(shè)計中，遞歸調(diào)用是

一種重要的特殊的設(shè)計方法，而棧又是數(shù)據(jù)結(jié)構(gòu)中很重要的一種數(shù)據(jù)結(jié)構(gòu)，本文通過對遞歸和棧的簡單討論，進而發(fā)掘出它們之間的內(nèi)在聯(lián)系，更好的掌握遞歸，以便設(shè)計出更高效的程序。

關(guān)鍵詞：程序設(shè)計；遞歸；棧；數(shù)據(jù)結(jié)構(gòu)

中圖分類號：TP311.5

計算機程序設(shè)計語言中，遞歸調(diào)用是一種重要的結(jié)構(gòu)，可以使復(fù)雜的問題簡單化，編程邏輯清晰，但卻很難理解在計算機內(nèi)部其真實的執(zhí)行過程。棧是數(shù)據(jù)結(jié)構(gòu)中的一種重要的類型，在計算機算法中有著舉足輕重的作用。本文將借助C語言來探討兩者之間的內(nèi)在聯(lián)系。

1 什么是遞歸調(diào)用

在程序設(shè)計中，遞歸調(diào)用是一種特殊的嵌套調(diào)用，是某個函數(shù)調(diào)用其本身，而不是調(diào)用另外一個函數(shù)。遞歸是一種思想，只不過在程序中，是依靠函數(shù)嵌套這個特性來實現(xiàn)的。

遞歸調(diào)用就是在當(dāng)前的函數(shù)中調(diào)用當(dāng)前的函數(shù)并傳遞相應(yīng)的參數(shù)（如果需要參數(shù)），這是一個動作，這一動作是層層進行的，直到滿足一定情況的時候，才停止遞歸調(diào)用，開始從最后一個遞歸調(diào)用返回。

上述描述中，“直到滿足一定情況的時候，才停止遞歸調(diào)用，開始從最后一個遞歸調(diào)用返回”是遞歸過程能正常運行的關(guān)鍵，否則將進入死鎖狀態(tài)，直到資源耗盡。

下面看一個C語言中遞歸調(diào)用的一個實例，用于求解n！的遞歸調(diào)用函數(shù)定義：

這個函數(shù)叫做fact，需要一個長整型參數(shù)n，返回值亦是長整型。在fact函數(shù)內(nèi)部自己調(diào)用了自己（斜體字部分），這個就是一個典型的遞歸調(diào)用。其中的（n==0||n==1）就是結(jié)束遞歸從而進行值返回的條件。return 1L是結(jié)束遞歸后返回一個值1L。

這個函數(shù)過程符合階乘的定義，邏輯清晰，可是計算機編譯系統(tǒng)如何執(zhí)行這個程序呢？換句話說我們能不能使用三種基本的程序結(jié)構(gòu)（順序、選擇、循環(huán)）來實現(xiàn)這個遞歸過程，使其不再抽象呢？

2 棧結(jié)構(gòu)及其基本算法

在計算機領(lǐng)域，棧是一個不容忽視的數(shù)據(jù)結(jié)構(gòu)。棧是一種數(shù)據(jù)項按序排列的數(shù)據(jù)結(jié)構(gòu)，只能在一端（稱為棧頂（TOP））對數(shù)據(jù)項進行插入和刪除操作的線性表，另一端（稱為棧底（BOTTOM））固定。棧用來滿足后進先出（Last-In/First-Out）的需求。?？煞譃轫樞驐：玩準綏＃疚囊皂樞驐槔懻撨f歸與棧的關(guān)系。

進棧和出棧是棧結(jié)構(gòu)的基本操作，下面給出原型：

2.1 進棧（PUSH）算法

（1）若TOP≥MAXLEN時，則給出溢出信息，作出錯處理（進棧前首先檢查棧是否已滿，滿則溢出；不滿則作（2））；（2）置TOP=TOP+1（棧指針加1，指向進棧地址）；（3）S（TOP）=X，結(jié)束（X為新進棧的元素）。

2.2 出棧（POP）算法

（1）若TOP=BOTTOM，則給出下溢信息，作出錯處理（出棧前先檢查是否已為空棧，空則下溢；不空則作（2））；（2）X=S（TOP），（出棧后的元素賦給X）：（3）TOP=TOP-1，結(jié)束（棧指針減1，指向棧頂）。

3 利用棧結(jié)構(gòu)，模擬遞歸過程，求解n！

3.1 我們回顧一下階乘的遞歸性定義：n！=n*（n-1）?。╪>=0，n為整數(shù)），特別的，規(guī)定0！=1。

即：若給定一個正整數(shù)n（n>=1），則n的階乘為n與n-1的階乘的乘積，我們?nèi)羟蟮胣-1的階乘，則n的階乘可求解；n-1的階乘可通過n-2的階乘求得；n-2的階乘可通過n-3的階乘求得；以此類推，n-m（m

那么什么時候可以求得一個具體的數(shù)值呢？當(dāng)n-（m+i）=0時，由階乘定義可知，其值為1，即n-（m+i）的階乘為1，進而求得n-（m+i-1）的階乘；n-（m+i-2）的階乘；n-（m+i-3）的階乘；直至求得n的階乘。

3.2 我們利用棧具有的后進先出的性質(zhì)，在上訴求解n-m階乘時，將n-m進棧（PUSH），繼續(xù)求解n-（m+1）階乘，亦將n-（m+1）進棧（PUSH），繼續(xù)求解n-（m+2）的階乘，亦將n-（m+2）進棧，直至n-（m+i）=0時，其階乘值可求得為0！=1，停止進棧，開始出棧，將n-（m+i-1）出棧，則n-（m+i-1）階乘值可求，再將n-（m+i-2）出棧，則n-（m+i-2）階乘值可求，以此類推直至將n出棧，最終求得n的階乘值。

3.3 主函數(shù)程序清單如下：

在程序設(shè)計中，遞歸是一種特殊的結(jié)構(gòu)，使用好遞歸結(jié)構(gòu)能設(shè)計出簡潔明了的程序，因此加深對遞歸調(diào)用的理解是很有必要的。通過上面的分析，我們知道，可以使用循環(huán)結(jié)構(gòu)和棧結(jié)構(gòu)模擬遞歸調(diào)用的過程，而當(dāng)我們在程序設(shè)計中使用遞歸調(diào)用時，實際上是由C編譯系統(tǒng)自動建立棧結(jié)構(gòu)，才能保證程序的運行。遞歸的次數(shù)雖然沒有嚴格的限制，但在實際設(shè)計中遞歸的次數(shù)過多，由于要不斷進行進棧操作，就要消耗大量的內(nèi)存空間，時間消耗也會增多，因此要做好預(yù)判，估算好時間復(fù)雜度和空間復(fù)雜度以提高程序的運行效率。

參考文獻：

[1]嚴蔚敏，吳偉民.數(shù)據(jù)結(jié)構(gòu)（C語言版）[M].北京：清華大學(xué)出版社，2011.

[2]譚浩強.C語言程序設(shè)計（第四版）[M].北京：清華大學(xué)出版社，2012.

作者簡介：李春生（1974.03-），男，教師，講師，研究方向：計算機軟件。

作者單位：遼寧石化職業(yè)技術(shù)學(xué)院 南校區(qū)，遼寧錦州 121000