Java基礎(chǔ)學(xué)習(xí):java怎么遞歸函數(shù)

Java基礎(chǔ)學(xué)習(xí):java怎么遞歸函數(shù)

長沙一度軟件培訓(xùn)      2022-04-30 16:49:01     25

Java基礎(chǔ)學(xué)習(xí):java怎么遞歸函數(shù),  遞歸的思想  以此類推是遞歸的基本思想?! 【唧w來講就是把規(guī)模大的問題轉(zhuǎn)化為規(guī)模小的相似的子問題來解決。在函數(shù)實(shí)現(xiàn)時(shí)

課程價(jià)格 請(qǐng)咨詢

上課時(shí)段: 授課校區(qū):

詳細(xì)介紹


  遞歸的思想


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


  具體來講就是把規(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)用)


  存在一種簡(jiǎn)單情境,可以使遞歸在簡(jiǎn)單情境下退出。(遞歸出口)


  遞歸三要素:


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


  總是在嘗試將一個(gè)問題化簡(jiǎn)到更小的規(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í)簡(jiǎn)單而典型的例子,階乘的遞推公式為: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è)更簡(jiǎ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)和條理非常清晰。


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


Java基礎(chǔ)學(xué)習(xí)

培訓(xùn)啦提醒您:交易時(shí)請(qǐng)核實(shí)對(duì)方資質(zhì),對(duì)于過大宣傳或承諾需謹(jǐn)慎!任何要求預(yù)付定金、匯款等方式均存在風(fēng)險(xiǎn),謹(jǐn)防上當(dāng)。