java培訓(xùn)知識(shí)-遞歸.doc

Java培訓(xùn)專家傳智播客遞歸遞歸（Recursion）遞歸：在數(shù)學(xué)與計(jì)算機(jī)科學(xué)中，是指在函數(shù)的定義中使用函數(shù)自身的方法。遞歸一詞還較常用于描述以自相似方法重復(fù)事物的過(guò)程。我舉個(gè)例子來(lái)說(shuō)明這個(gè)問(wèn)題，大家都應(yīng)該聽(tīng)過(guò)這樣一個(gè)故事： 從前有座山，山里有座廟，廟里有個(gè)老和尚，正在給小和尚講故事呢！故事是什么呢？“從前有座山，山里有座廟，廟里有個(gè)老和尚，正在給小和尚講故事呢！故事是什么呢？從前有座山，山里有座廟，廟里有個(gè)老和尚，正在給小和尚講故事呢！故事是什么呢？”。在這里，“從前有座山，山里有座廟，廟里有個(gè)老和尚，正在給小和尚講故事呢！故事是什么呢？”這個(gè)過(guò)程就可以用遞歸算法來(lái)描述。遞歸作為一種編程技巧在程序設(shè)計(jì)語(yǔ)言中存在，優(yōu)點(diǎn)是顯而易見(jiàn)的。它通常把一個(gè)大型復(fù)雜的問(wèn)題層層轉(zhuǎn)化為一個(gè)與原問(wèn)題相似的規(guī)模較小的問(wèn)題來(lái)求解，遞歸策略只需少量的程序就可描述出解題過(guò)程所需要的多次重復(fù)計(jì)算，大大地減少了程序的代碼量。遞歸的能力在于用有限的語(yǔ)句來(lái)定義對(duì)象的無(wú)限集合。一般來(lái)說(shuō)，遞歸需要有邊界條件、遞歸前進(jìn)段和遞歸返回段。當(dāng)邊界條件不滿足時(shí)，遞歸前進(jìn)；當(dāng)邊界條件滿足時(shí)，遞歸返回。 注意： (1) 遞歸就是在函數(shù)里調(diào)用自身； (2) 在使用遞歸策略時(shí)，必須有一個(gè)明確的遞歸結(jié)束條件，稱為遞歸出口。遞歸算法一般用于解決三類問(wèn)題： (1)數(shù)據(jù)的定義是按遞歸定義的。（Fibonacci函數(shù)） (2)問(wèn)題解法按遞歸算法實(shí)現(xiàn)。（回溯） (3)數(shù)據(jù)的結(jié)構(gòu)形式是按遞歸定義的。（樹(shù)的遍歷，圖的搜索）任何一種技巧都是一把雙刃劍，既然有優(yōu)點(diǎn)，肯定也存在著問(wèn)題，對(duì)此我們也要了解遞歸的缺點(diǎn)： 遞歸算法解題相對(duì)常用的算法如普通循環(huán)等，運(yùn)行效率較低。因此，應(yīng)該盡量避免使用遞歸，除非沒(méi)有更好的算法或者某種特定情況，遞歸更為適合的時(shí)候才使用遞歸。在遞歸調(diào)用的過(guò)程當(dāng)中系統(tǒng)為每一層的返回點(diǎn)、局部量等開(kāi)辟了棧來(lái)存儲(chǔ)。遞歸次數(shù)過(guò)多容易造成棧溢出等。遞歸舉例例1：計(jì)算5!分析：首先我們要明白n！代表什么意思。n! = 123n，假設(shè)得到的積是x，x就是n的階乘。如果采用普通的循環(huán)，我們可以用如下函數(shù)實(shí)現(xiàn)：class Factorial public static void main(String args) System.out.println(getFactorial(5);/求整型數(shù)據(jù)number的階乘public static int getFactorial(int number)/由于1乘以任何數(shù)等于任何數(shù)。所以，定義保存每次乘積結(jié)果的變量初始化為1.int sum = 1;/由于1乘以任何數(shù)等于任何數(shù)。所以，增量從2開(kāi)始即可。for(int x=2; x1時(shí)，結(jié)果為 number*(number-1)!在java語(yǔ)言中可用如下代碼如下：/求整型數(shù)據(jù)number的階乘public static int getFactorial(int number)if(number=1)return 1;elsereturn number*getFactorial(number-1);例2：計(jì)算斐波納契數(shù)列的第二十項(xiàng)的值。分析：首先，我們得知道什么的數(shù)列是斐波納契數(shù)列。如下：1，1，2，3，5，8，13，21，34，55，89這個(gè)數(shù)列則稱為“斐波納契數(shù)列”，其中每個(gè)數(shù)字都是“斐波納契數(shù)”。我們要求的是第二十項(xiàng)的值，所以，我們需要觀察規(guī)律。通過(guò)觀察可知：從第三個(gè)數(shù)起，每個(gè)數(shù)都是前兩數(shù)之和，那么，采用普通的做法，我們就可以實(shí)現(xiàn)求次數(shù)列的第二十項(xiàng)的值。class Fibonacci public static void main(String args) System.out.println(fibonacci(20);/求裴波那切數(shù)列的第二十項(xiàng)的值public static int fibonacci(int number)/前兩個(gè)數(shù)都是1int first = 1;int second = 1;/用于保存第n項(xiàng)的值int fib = 0;for(int x=3; x2時(shí)，結(jié)果為 第（number-1）項(xiàng)的值+第（number-2）的值在java語(yǔ)言中可用如下代碼如下：/求裴波那切數(shù)列的第二十項(xiàng)的值public static int fibonacci(int number)if(number=1 | number=2)return 1;elsereturn fibonacci(number-1)+fibonacci(number-2);通過(guò)上面的例子，我們可以看到，遞歸確實(shí)讓代碼看起來(lái)更簡(jiǎn)潔了。而且還好理解。但是，如果需要循環(huán)的次數(shù)太多的話，建議不要使用