遞歸的思想

　　以此類推是遞歸的基本思想。

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

　　遞歸的兩個(gè)條件

　　可以通過遞歸調(diào)用來縮小問題規(guī)模，且新問題與原問題有著相同的形式。（自身調(diào)用）

　　存在一種簡單情境，可以使遞歸在簡單情境下退出。（遞歸出口）

　　遞歸三要素：

　　一定有一種可以退出程序的情況；

　　總是在嘗試將一個(gè)問題化簡到更小的規(guī)模

　　父問題與子問題不能有重疊的部分

　　遞歸：自已（方法）調(diào)用自已

　　例子：用遞歸把目錄下所有的目錄及文件全部顯示出來

　　publicclassB{

　　publicstaticvoidmain(String[]args){

　　Filefile=newFile("f:\\123");

　　listAllFile(file);

　　}

　　publicstaticvoidlistAllFile(Filefile){

　　File[]strs=file.listFiles();

　　for(inti=0;i<strs.length;i++){

　　//判斷strs[i]是不是目錄

　　if(strs[i].isDirectory()){

　　listAllFile(strs[i]);//遞歸調(diào)用自己

　　System.out.println("目錄="+strs[i].getName());

　　}else{

　　System.out.println("文件名="+strs[i].getName());

　　}

　　}

　　}

　　}

　　遞歸算法的一般形式：

　　func(mode){

　　if(endCondition){//遞歸出口

　　end;

　　}else{

　　func(mode_small)//調(diào)用本身，遞歸

　　}

　　}

　　例子

　　求一個(gè)數(shù)的階乘是練習(xí)簡單而典型的例子，階乘的遞推公式為：factorial(n)=n*factorial(n-1)，其中n為非負(fù)整數(shù),且0!=1,1!=1

　　我們根據(jù)遞推公式可以輕松的寫出其遞歸函數(shù)：

　　publicstaticlongfactorial(intn)throwsException{

　　if(n<0)

　　thrownewException("參數(shù)不能為負(fù)！");

　　elseif(n==1||n==0)

　　return1;

　　else

　　returnn*factorial(n-1);

　　}

　　遞歸的過程

　　在求解6的階乘時(shí)，遞歸過程如下所示。

　　我們會(huì)驚奇的發(fā)現(xiàn)這個(gè)過程和棧的工作原理一致對(duì)，遞歸調(diào)用就是通過棧這種數(shù)據(jù)結(jié)構(gòu)完成的。整個(gè)過程實(shí)際上就是一個(gè)棧的入棧和出棧問題。然而我們并不需要關(guān)心這個(gè)棧的實(shí)現(xiàn)，這個(gè)過程是由系統(tǒng)來完成的。

　　那么遞歸中的“遞”就是入棧，遞進(jìn)；“歸”就是出棧，回歸。

　　我們可以通過一個(gè)更簡單的程序來模擬遞進(jìn)和回歸的過程：

　　/*

　　關(guān)于遞歸中遞進(jìn)和回歸的理解*/

　　publicstaticvoidrecursion_display(intn){

　　inttemp=n;//保證前后打印的值一樣

　　System.out.println("遞進(jìn):"+temp);

　　if(n>0){

　　recursion_display(--n);

　　}

　　System.out.println("回歸:"+temp);

　　}

　　遞歸的例子

　　斐波那契數(shù)列

　　斐波那契數(shù)列的遞推公式:Fib(n)=Fib(n-1)+Fib(n-2)，指的是如下所示的數(shù)列：

　　1、1、2、3、5、8、13、21.....

　　按照其遞推公式寫出的遞歸函數(shù)如下：

　　publicstaticintfib(intn)throwsException{

　　if(n<0)

　　thrownewException("參數(shù)不能為負(fù)！");

　　elseif(n==0||n==1)

　　returnn;

　　else

　　returnfib(n-1)+fib(n-2);

　　}

　　遞歸調(diào)用的過程像樹一樣，通過觀察會(huì)發(fā)現(xiàn)有很多重復(fù)的調(diào)用。

　　歸并排序

　　歸并排序也是遞歸的典型應(yīng)用，其思想：將序列分為若干有序序列（開始為單個(gè)記錄），兩個(gè)相鄰有序的序列合并成一個(gè)有序的序列，以此類推，直到整個(gè)序列有序。

　　//遞歸過程是：在遞進(jìn)的過程中拆分?jǐn)?shù)組，在回歸的過程合并數(shù)組

　　publicstaticvoidmergeSort(int[]source,int[]temp,intfirst,intlast){

　　if(first<last){

　　intmid=(first+last)/2;

　　mergeSort(source,temp,first,mid);//歸并排序前半個(gè)子序列

　　mergeSort(source,temp,mid+1,last);//歸并排序后半個(gè)子序列

　　merge(source,temp,first,mid,last);//在回歸過程中合并

　　}elseif(first==last){//待排序列只有一個(gè)，遞歸結(jié)束

　　temp[first]=source[first];

　　}

　　同樣調(diào)用過程向樹一樣，但是它并沒有重復(fù)調(diào)用的問題。在遞進(jìn)的過程中拆分?jǐn)?shù)組，在回歸的過程合并數(shù)組。通過遞歸來實(shí)現(xiàn)歸并排序，程序結(jié)構(gòu)和條理非常清晰。

　   以上就是動(dòng)力節(jié)點(diǎn)Java培訓(xùn)機(jī)構(gòu)小編介紹的“Java基礎(chǔ)學(xué)習(xí)：java怎么遞歸函數(shù)”的內(nèi)容，希望對(duì)大家有幫助，如有疑問，請(qǐng)?jiān)诰€咨詢，有專業(yè)老師隨時(shí)為你服務(wù)。