在JAVA中用遞歸解決的問題解析

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

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

中圖分類號：TP301.6

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

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

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

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

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

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

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

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

遞歸分為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ù)中要做到如下幾點：

（1）寫出遞歸的出口。

（2）解決當前要解決的問題——相當與階層問題中的（n）。

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

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

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

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

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

參考文獻：

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

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

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

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

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

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