淺析遞歸函數在C++語言中的實現

陳穎鑫，李主國

（1.中南財經政法大學，湖北 武漢 430073；2.湖北廣播電視大學，湖北 武漢 430073）

淺析遞歸函數在C++語言中的實現

1陳穎鑫，2李主國

（1.中南財經政法大學，湖北 武漢 430073；2.湖北廣播電視大學，湖北 武漢 430073）

本文結合生活實際探討了遞歸函數的概念，并舉例說明了遞歸函數的具體編寫方法，研究了遞歸的調用機制，最后總結了遞歸函數的利弊，提出要適當地使用遞歸思想的原則。

遞歸；函數；程序設計；C++語言

1 .引言

如果定義一個概念或事物需要用到這個概念或事物本身，我們稱它的定義是遞歸的（Recursive）。例如，下面這個故事：

從前有座山，山上有座廟，廟里有個老和尚，正在給小和尚講故事！故事是什么呢？“從前有座山，山上有座廟，廟里有個老和尚，正在給小和尚講故事呢！故事是什么呢？‘從前有座山，山上有座廟，廟里有個老和尚，正在給小和尚講故事呢！故事是什么呢？……’”

當聽到這個故事，一般人都會感覺到無聊之極。然而，數學上確實需要這種“無聊”呢，例如，有很多概念是用它自己來定義的，像n的階乘是這樣定義的：n的階乘等于n乘以n-1的階乘。如果這樣就算定義完了，恐怕跟上面那個故事有異曲同工之妙了：n-1的階乘是什么？是n-1乘以n-2的階乘。那n-2的階乘又是什么？這樣下去，永無休止了。因此，需要定義一個最關鍵的基礎條件：0的階乘等于1。

實質上，遞歸函數使用的是數學歸納法的理念，即初始條件和遞推兩者不可或缺。遞歸，是函數實現的一個很重要的環節或者方法，很多程序都或多或少的使用了遞歸函數。遞歸的意思就是函數自己調用自己本身，或者在調用的下級函數中調用自己，不管是直接調用，還是間接調用。

2 .遞歸函數編程

把上面的階乘定義用C++語言來實現，可以寫成這樣：

從程序可以看到，我們采用遞歸函數的方法編程的時候，只需要把初始條件和遞推兩者表達清楚，基本上就可以完成任務了。計算機會根據你的合理設計，自行完成遞歸的算法過程。

不妨再來看幾個問題：

A）Fibonacci數列，它是這樣定義的：

①fib(1)=1

②fib(2)=1

（1）液質條件：Thermo Scientific LCQ液質聯用儀，XbridgeTM-C18色譜柱（250 mm×4.6 mm，5 μm）；填充劑為十八烷基硅烷鍵合硅膠；流動相為乙腈-0.5%氨水溶液，等度洗脫（80∶20），體積流量0.5 mL/min；檢測波長235 nm；柱溫25 ℃；進樣量5 μL。ESI離子源，正離子檢出模式，掃描范圍m/z 95～800。

③fib(n)=fib(n-1)+fib(n-2)

用C++語言編程的實現：

B）使用輾轉相除法求兩個正整數a和b的最大公約數：

①如果a能被b整除，則最大公約數是b。

②否則，最大公約數等于b和a%b的最大公約數。（a%b表示a被b除的余數）

用C++語言編程的實現：

上面兩個問題看似毫不相干，它們之間卻有一個有意思的聯系（即Lamé定理）：如果輾轉相除法需要k步來計算兩個數的最大公約數，那么這兩個數之中較小的一個必然大于等于Fibonacci數列的第k項。

C）猴子吃桃問題

猴子第一天摘下若干桃子，當即吃了一半，還不過癮，又多吃了一個。第二天早上又將剩下的桃子吃掉一半，又多吃了一個。以后每天早上都吃了前一天剩下的一半零一個。到第10天早上想再吃時，見只剩一個桃子了。試求第一天至少摘下多少桃子？

下面這個程序可以求出每天的桃子數目：

D）漢諾塔游戲

有三根柱子，在一根柱子上從下往上按照大小順序摞著n片黃金圓盤。需要把圓盤從下面開始按大小順序重新擺放在另一根柱子上。并且規定，在小圓盤上不能放大圓盤，在三根柱子之間一次只能移動一個圓盤。

使用C++語言可以這么實現：

上述若干問題均是以遞歸的形式描述的，所以很容易采用遞歸方法編程實現。從以上幾個問題的求解可以看出，凡使用遞歸解法，一定要設置好初始條件，再就是對遞歸過程的處理。初始條件是遞歸得以完成的終結條件，而遞歸過程則是將復雜問題逐步簡化為較簡單一點的問題，直到歸結為終結條件。

3 .遞歸程序的運行機制

遞歸之所以能實現，是因為函數的每個執行過程都在棧中有自己的形參和局部變量的拷貝，這些拷貝和函數的其他執行過程毫不相干。這種機制依靠棧來實現，它是當代大多數程序設計語言實現子程序結構的基礎。假定某個調用函數調用了一個被調用函數，再假定被調用函數又反過來調用了調用函數。這第二個調用就被稱為調用函數的遞歸，因為它發生在調用函數的當前執行過程運行完畢之前。而且，因為這個原先的調用函數、現在的被調用函數在棧中較低的位置有它獨立的一組參數和自變量，原先的參數和變量將不受影響，所以遞歸能正常工作。

程序員需保證遞歸函數不會隨意改變靜態變量和全局變量的值，以避免在遞歸下降過程中的上層函數出錯。程序員還必須確保有一個終止條件來結束遞歸下降過程，并且返回到頂層。

自己調用本身，這樣就是遞歸。那么有人可能會想，這不是死循環嗎？的確，如果不小心，很容易造成死循環。因此，在遞歸函數中，一定要保證遞歸得以下降為較簡單的問題，如果遞歸不能下降，函數將會形成死循環。

在某些場合，使用遞歸比使用循環要簡單得多。而且有些題目，一看就知道應該使用遞歸而不是循環來處理。相反，有些問題則不需要使用遞歸過程來解決。比如，階乘完全可以采用簡單的循環來處理：

程序如此改寫后，可以減小計算機系統的堆棧開銷，改善程序所使用的空間及運行效率。

4 .結論

遞歸，在數學和計算機科學中都是一種重要的求解問題的方法。遞歸程序設計思想是計算機編程思想中分治思想的典型代表。很多看似復雜或者難于理清頭緒的問題使用遞歸方法能以簡單易懂的形式一下子得到解決。

但是，凡事有利必有弊，我們需要適當地使用遞歸函數，切不可盲目濫用。基于遞歸函數的運行機制，某些能夠采用循環的方法直接實現的過程，可以避免使用遞歸算法，以改善程序的運行效率。

[1] 譚浩強. C++程序設計[M]. 北京：清華大學出版社，2004.

[2] 鄭莉. C++語言程序設計[M]. 北京：清華大學出版社，2003.

[3] 黃欣陽，等. 如何用遞歸方法進行程序設計[J]. 福建電腦，2011，（6）.

[4] 邵利平. 程序語言教學中的遞歸程序思維培養[J]. 電腦知識與技術，2011，（29）.

Simple Analysis of the Realization of Recursive Function in C++ Language

CHEN Ying-xin, LI Zhu-guo

In this Paper, the concept of Recursive Function is studied combined with daily life. The way to program recursive functions is shown by samples, and its call mechanism is analyzed. The benefit and disadvantage of these functions are concluded, while the principle to use recursive thought properly is also proposed.

Recursion; Function; Programming; C++ Language

TP311.1

A

1008-7427（2012）09-0159-02

2012-05-04