摘 要：遞歸就是循環(huán)，只不過要有條件變量作為最終返回。通常需要把一個大型復(fù)雜的問題層層轉(zhuǎn)化為一個與原問題相似的規(guī)模較小的問題來求解，遞歸策略只需少量的程序就可描述出解題過程所需要的多次重復(fù)計算，大大地減少了程序的代碼量。

關(guān)鍵詞：遞歸；算法；排列組合

中圖分類號：TP301.6

遞歸是一種非常接近自然思維的思想，其實了解多了以后，用起遞歸來是非常自然的，但不是每個場合使用遞歸都是合適的，簡單的來說，遞歸問題，可以劃分為一個或多個子問題，而處理子問題的規(guī)則與處理原問題的規(guī)則是一樣的，在我們編程的過程中，常常會碰到這樣一些問題，比如：有n個數(shù)，要從其中取出m（m<=n）個數(shù)，列出所有可能的組合。所以一般來說，會使用循環(huán)實現(xiàn)，但是邏輯復(fù)雜，不容易調(diào)試。但是使用遞歸算法，卻大大地簡化程序。

遞歸的原理，其實就是一個棧（stack），比如求5的階乘，要知道5的階乘，就要知道4的階乘，4又要是到3的，以此類推，所以遞歸式就先把5的階乘表示入棧，在把4的入棧，直到最后一個，之后呢在從1開始出棧，看起來很麻煩，確實很麻煩，他的好處就是寫起代碼來，十分的快，而且代碼簡潔，其他就沒什么好處了，運(yùn)行效率出奇的慢。

使用遞歸實現(xiàn)一個算法時，首先要對問題進(jìn)行降級處理，就是對于處理n的問題，要轉(zhuǎn)化為n-1或者n-2，…的問題。其次，就是要確定遞歸結(jié)束條件。如果沒有遞歸結(jié)束條件，程序就無法結(jié)束，導(dǎo)致系統(tǒng)資源消耗殆盡。遞歸處理代碼簡潔外，還有個好處，就是你在循環(huán)前，不知道循環(huán)的層次是多少時，用遞歸比較方便，譬如遍歷樹、遍歷磁盤文件等，在循環(huán)前，你根本不知道磁盤有多少個文件夾和文件，調(diào)用遞歸無需事先知道這些，只要找到最后文件夾時返回就可以了。但是遞歸也有缺點(diǎn)，就是消耗棧資源太多了。

實現(xiàn)遞歸算法的步驟，大致可以歸結(jié)為以下幾點(diǎn)：

（1）歸納出“遞推”規(guī)則。

（2）找出“遞歸結(jié)束”的條件——這一點(diǎn)很重要，因為如果沒有合理終止遞歸的條件約束，程序?qū)⑾萑霟o窮遞歸中，然后導(dǎo)致棧溢出。

（3）實現(xiàn)算法。

在做遞歸算法的時候，一定要把握住出口，也就是做遞歸算法必須要有一個明確的遞歸結(jié)束條件。這一點(diǎn)是非常重要的。其實這個出口是非常好理解的，就是一個條件，當(dāng)滿足了這個條件的時候我們就不再遞歸了。

遞歸分為2種，直接遞歸和間接遞歸。直接遞歸，比如方法A內(nèi)部調(diào)用方法A自身；間接遞歸，比如方法A內(nèi)部調(diào)用方法B，方法B內(nèi)部調(diào)用方法C，方法C內(nèi)部調(diào)用方法A。

其實所有的遞歸問題都可以看成是階層問題

所要解決的整個問題（整個遞歸函數(shù)）看成是f（n）.在這個遞歸函數(shù)中要做到如下幾點(diǎn)：

（1）寫出遞歸的出口。

（2）解決當(dāng)前要解決的問題——相當(dāng)與階層問題中的（n）。

（3）遞歸下去（調(diào)用自身）解決相同的但規(guī)模要小的又一問題——相當(dāng)于f（n-1）。

如果函數(shù)實現(xiàn)了這幾點(diǎn)，那么遞歸算法也就基本成功。不過有些問題他的f（n-1）可能要調(diào)用幾次（可能每次的參數(shù)還不同），因為他在實現(xiàn)（n）的時候要先調(diào)用f（n-1）為前提。這樣的例子很多.比如梵塔問題就是這種情況?？偠灾?，你要懂的把復(fù)雜的遞歸問題遷移成簡單的階層遞歸問題，這時候問題就比較好理解和解決。

遞歸，就是自己反復(fù)調(diào)用自己的方法，直到出現(xiàn)最終結(jié)果。也可以理解為將原有的大的任務(wù)分解為小的任務(wù)，然后計算小的任務(wù)，最后合并為大的任務(wù)。從上面這段程序可以知道，要求數(shù)組的全排列這樣子考慮，固定一個數(shù)，求子數(shù)組的全排列，比如固定1，那么要求2，3，4的全排列，子數(shù)組又可以當(dāng)做一個新的數(shù)組用上面的方法，固定2，求3，4的全排列，以此類推。接下來確定循環(huán)的次數(shù)，數(shù)組為1，2，3，4時，需要分別固定1，2，3，4，所以循環(huán)4次，同理子數(shù)組分別循環(huán)3，2，1次，可以發(fā)現(xiàn)循環(huán)次數(shù)即為數(shù)組的元素個數(shù)這個規(guī)律。這個遞歸的終止條件就是到達(dá)循環(huán)次數(shù)后跳出方法至上層方法，繼續(xù)外層循環(huán)。說白了，遞歸就是有規(guī)律地將一個算法切割成同等規(guī)律的子算法重復(fù)運(yùn)算，達(dá)到終止條件后返回上層方法。

以上這個算法的思想是：如果這個樹是空，則返回0；否則先求左邊樹的深度，再求右邊數(shù)的深度，然后對這兩個值進(jìn)行比較哪個大就取哪個值+1。對于遞歸，最好的理解方式便是從函數(shù)的功能意義的層面來理解。了解一個問題如何被分解為它的子問題，這樣對于遞歸函數(shù)代碼也就理解了。這里有一個誤區(qū)（我也曾深陷其中），就是通過分析堆棧，分析一個一個函數(shù)的調(diào)用過程、輸出結(jié)果來分析遞歸的算法。這是十分要不得的，這樣只會把自己弄暈，其實遞歸本質(zhì)上也是函數(shù)的調(diào)用，調(diào)用的函數(shù)是自己或者不是自己其實沒什么區(qū)別。在函數(shù)調(diào)用時總會把一些臨時信息保存到堆棧，堆棧只是為了函數(shù)能正確的返回，僅此而已。我們只要知道遞歸會導(dǎo)致大量的函數(shù)調(diào)用，大量的堆棧操作就可以了。

所以說遞歸的基本思想是把規(guī)模大的問題轉(zhuǎn)化為規(guī)模小的相似的子問題來解決。在函數(shù)實現(xiàn)時，因為解決大問題的方法和解決小問題的方法往往是同一個方法，所以就產(chǎn)生了函數(shù)調(diào)用它自身的情況。另外這個解決問題的函數(shù)必須有明顯的結(jié)束條件，這樣就不會產(chǎn)生無限遞歸的情況了。

參考文獻(xiàn)：

[1]童寧江，古輝.一類分形曲線遞歸算法的新設(shè)計[J].科學(xué)技術(shù)與工程，2011（20）.

[2]宋美英.基于C語言的冒泡排序算法探討[J].現(xiàn)代計算機(jī)（專業(yè)版），2011（29）.

[3]晏素芹.淺析程序設(shè)計中的遞歸算法[J].內(nèi)蒙古科技與經(jīng)濟(jì)，2010（17）.

[4]黎佩南.一種快速排序算法的實現(xiàn)及其應(yīng)用[J].電訊技術(shù)，2012（02）.

作者簡介：陶姿邑（1985-），女，陜西洛南人，助理工程師，本科，研究方向：計算機(jī)網(wǎng)絡(luò)。

作者單位：陜西中醫(yī)學(xué)院，陜西咸陽 712046