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

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