java新人基礎入門之遞歸調用
一、遞歸概念
遞歸本質：程序調用自身的編程技巧叫做遞歸。
程序調用自身的編程技巧稱為遞歸（ recursion）。遞歸做為一種算法在程序設計語言中廣泛應用。 一個過程或函數在其定義或說明中有直接或間接調；
用自身的一種方法，它通常把一個大型復雜的問題層層轉化為一個與原問題相似的規模較小的問題來求解，遞歸策略隻需少量的程序就可描述出解題過；
程所需要的多次重復計算，大大地減少瞭程序的代碼量。遞歸的能力在於用有限的語句來定義對象的無限集合。
二、遞歸的三個條件：
- 邊界條件
- 遞歸前進段
- 遞歸返回段
當邊界條件不滿足時，遞歸前進；當邊界條件滿足時，遞歸返回。
下面通過兩個示例程序來說明：
使用Java代碼求5的階乘。（5的階乘=5*4*3*2*1）
package org.wxp.recursion;
/**
* 計算5的階乘(result = 5*4*3*2*1)
* @author Champion.Wong
*
*
*/
public class Test01 {
public static void main(String[] args) {
System.out.println(f(5));
}
public static int f(int n) {
if (1 == n)
return 1;
else
return n*f(n-1);
}
}
此題中，按照遞歸的三個條件來分析：
(1)邊界條件：階乘，乘到最後一個數，即1的時候，返回1，程序執行到底；
(2)遞歸前進段：當前的參數不等於1的時候，繼續調用自身；
(3)遞歸返回段：從最大的數開始乘，如果當前參數是5，那麼就是5*4，即5*(5-1)，即n*(n-1)
使用Java代碼求數列：1，1，2，3，5，8……第40位的數
package org.wxp.recursion;
/**
* 求數列：1，1，2，3，5，8......第40位的數
* @author Champion.Wong
*
*/
public class Test_02_Fibonacci {
public static void main(String[] args) {
System.out.println(f(6));
}
public static int f(int n ) {
if (1== n || 2 == n)
return 1;
else
return f(n-1) + f(n-2);
}
}
此題的突破口在：從第3位數開始，本位數是前兩位數的和。要計算第多少位的值，那麼就需要將位數作為參數傳進方法進行計算。
(1)首先，當位數為1和2時，當前返回的值應該是1；
(2)然後，當位數為3時，返回值應該=2=1+1；
當位數為4時，返回值=3=2+1；
當位數為5時，返回值=5=3+2；
當位數為6時，返回值=8=5+3；
……
(3)由(2)得知，大於等於3的情況下，當前位數（n）的數值=f(n-1)+f(n-2)
三、非遞歸方法實現（迭代方法）
迭代本質：利用變量的原值推算出變量的一個新值，迭代就是A不停的調用B.
通過觀察推導，找到解決問題的方法，發現其中的規律，將其轉化成程序語言表達出來。
本質：使用合適的數據類型變量代替問題中的數據，將解決問題的方法轉化為符合程序語言的邏輯。
public class Fab{
public static void main( String[] args){
System.out.println(f(20));
}
public static long f(int index){
if(index == 1 || index == 2){
return 1;
}
long f1 = 1L;
long f2 = 1L;
long f = 0;
for(int i=0; i<index; i++){
f = f1 + f2;
f1 = f2;
f2 = f;
}
return f;
}
}
遞歸其實是方便瞭程序員難為瞭機器，遞歸可以通過數學公式很方便的轉換為程序。其優點就是易理解，容易編程。但遞歸是用棧機制實現的，每深入一層，都要占去一塊棧數據區域，對嵌套層數深的一些算法，遞歸會力不從心，空間上會以內存崩潰而告終，而且遞歸也帶來瞭大量的函數調用，這也有許多額外的時間開銷。所以在深度大時，它的時空性就不好瞭。（會占用大量的內存空間）
而迭代雖然效率高，運行時間隻因循環次數增加而增加，沒什麼額外開銷，空間上也沒有什麼增加，但缺點就是不容易理解，編寫復雜問題時困難。
能不用遞歸就不用遞歸，遞歸都可以用迭代來代替。（要辯證的看待這個問題，深度不大，還是可以采用遞歸的）。
總結
到此這篇關於java新人基礎入門之遞歸調用的文章就介紹到這瞭,更多相關java遞歸調用內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！