快捷導(dǎo)航

Java遞歸算法詳解(動(dòng)力節(jié)點(diǎn)整理)

更新時(shí)間：2017年03月29日 16:48:07 投稿：mrr

Java遞歸算法是基于Java語言實(shí)現(xiàn)的遞歸算法。遞歸算法對(duì)解決一大類問題很有效，它可以使算法簡(jiǎn)潔和易于理解。接下來通過本文給大家介紹Java遞歸算法相關(guān)知識(shí)，感興趣的朋友一起學(xué)習(xí)吧

遞歸算法是一種直接或者間接調(diào)用自身函數(shù)或者方法的算法。Java遞歸算法是基于Java語言實(shí)現(xiàn)的遞歸算法。遞歸算法的實(shí)質(zhì)是把問題分解成規(guī)模縮小的同類問題的子問題，然后遞歸調(diào)用方法來表示問題的解。遞歸算法對(duì)解決一大類問題很有效，它可以使算法簡(jiǎn)潔和易于理解。

遞歸算法解決問題的特點(diǎn)：

1）遞歸就是方法里調(diào)用自身。

　 2）在使用遞增歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸出口。

　 3）遞歸算法解題通常顯得很簡(jiǎn)潔，但遞歸算法解題的運(yùn)行效率較低。所以一般不提倡用遞歸算法設(shè)計(jì)程序。

　 4）在遞歸調(diào)用的過程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開辟了棧來存儲(chǔ)。遞歸次數(shù)過多容易造成棧溢出等，所以一般不提倡用遞歸算法設(shè)計(jì)程序。

　遞歸算法所體現(xiàn)的“重復(fù)”一般有三個(gè)要求：

　一是每次調(diào)用在規(guī)模上都有所縮小(通常是減半)；

　二是相鄰兩次重復(fù)之間有緊密的聯(lián)系，前一次要為后一次做準(zhǔn)備(通常前一次的輸出就作為后一次的輸入)；

　三是在問題的規(guī)模極小時(shí)必須用直接給出解答而不再進(jìn)行遞歸調(diào)用，因而每次遞歸調(diào)用都是有條件的(以規(guī)模未達(dá)到直接解答的大小為條件)，無條件遞歸調(diào)用將會(huì)成為死循環(huán)而不能正常結(jié)束。

為了理解遞歸算法，現(xiàn)舉一個(gè)實(shí)例說明如下：

問題描述：

求解Fibonacci數(shù)列的第10個(gè)位置的值？（斐波納契數(shù)列（Fibonacci Sequence），又稱黃金分割數(shù)列，指的是這樣一個(gè)數(shù)列：1、1、2、3、5、8、13、21、……在數(shù)學(xué)上，斐波納契數(shù)列以如下被以遞歸的方法定義：F0=0，F(xiàn)1=1，F(xiàn)n=F(n-1)+F(n-2)（n>=2，n∈N*））

Java代碼清單：

package com.bjpowernode.test; 
 
 public classFab { 
 
 public static void main(String args[]){ 
 System.out.println(fab(5)); 
 } 
 private static int fab(int index){ 
 if(index==1 || index==2){ 
  return 1; 
 }else{ 
  return fab(index-1)+fab(index-2); 
 } 
 } 
 }

程序分析：

這個(gè)實(shí)例是非常經(jīng)典的實(shí)例，主要是利用遞歸實(shí)現(xiàn)了Fibonacci數(shù)列。這個(gè)遞歸算法的出口是在

 if(index==1 || index==2){ 
 return 1; 
 }

這個(gè)代碼段上，如果程序的index符合條件就會(huì)停止進(jìn)行遞歸。所以這個(gè)程序的運(yùn)行流程是：

程序分析到這里，遞歸的實(shí)現(xiàn)也就完成了，讀者可以自己簡(jiǎn)單的做個(gè)demo，感受一下這個(gè)算法的精妙之處，其實(shí)很多人都在說算法難，難于上青天，其實(shí)掌握算法的根才是最重要的，什么是算法的根呢，就拿這個(gè)遞歸算法來說吧，我感覺這個(gè)根就是那個(gè)出口，只要找到這個(gè)出口所在，那么算法自然而然就能水到渠成了。

以上所述是小編給大家介紹的Java遞歸算法詳解(動(dòng)力節(jié)點(diǎn)整理)，希望對(duì)大家有所幫助，如果大家有任何疑問請(qǐng)給我留言，小編會(huì)及時(shí)回復(fù)大家的。在此也非常感謝大家對(duì)腳本之家網(wǎng)站的支持！

您可能感興趣的文章: