模板
教程
環境
性能
功能
管理
什么是遞歸算法:對遞歸的理解
一、基本概念
遞歸算法是一種直接或者間接調用自身函數或者方法的算法。Java遞歸算法是基于Java語言實現的遞歸算法。遞歸算法的實質是把問題分解成規?？s小的同類問題的子問題，然后遞歸調用方法來表示問題的解。遞歸算法對解決一大類問題很有效，它可以使算法簡潔和易于理解。遞歸算法，其實說白了，就是程序的自身調用。它表現在一段程序中往往會遇到調用自身的那樣一種coding策略，這樣我們就可以利用大道至簡的思想，把一個大的復雜的問題層層轉換為一個小的和原問題相似的問題來求解的這樣一種策略。遞歸往往能給我們帶來非常簡潔非常直觀的代碼形勢，從而使我們的編碼大大簡化，然而遞歸的思維確實很我們的常規思維相逆的，我們通常都是從上而下的思維問題， 而遞歸趨勢從下往上的進行思維。這樣我們就能看到我們會用很少的語句解決了非常大的問題，所以遞歸策略的最主要體現就是小的代碼量解決了非常復雜的問題。
遞歸算法解決問題的特點：
1)遞歸就是方法里調用自身。
2)在使用遞增歸策略時，必須有一個明確的遞歸結束條件，稱為遞歸出口。
3)遞歸算法解題通常顯得很簡潔，但遞歸算法解題的運行效率較低。所以一般不提倡用遞歸算法設計程序。
4)在遞歸調用的過程當中系統為每一層的返回點、局部量等開辟了棧來存儲。遞歸次數過多容易造成棧溢出等，所以一般不提倡用遞歸算法設計程序。
在做遞歸算法的時候，一定要把握住出口，也就是做遞歸算法必須要有一個明確的遞歸結束條件。這一點是非常重要的。其實這個出口是非常好理解的，就是一個條件，當滿足了這個條件的時候我們就不再遞歸了。
二、程序示例
?、凫巢{契數列(Fibonacci Sequence)
問題描述：求解Fibonacci數列的第n個位置的值?(斐波納契數列(Fibonacci Sequence)，又稱黃金分割數列，指的是這樣一個數列：1、1、2、3、5、8、13、21、……在數學上，斐波納契數列以如下被以遞歸的方法定義：F1=1,F2=1,Fn=F(n-1)+F(n-2)(n>2,n∈N*))。
求解代碼：
[java] view plaincopyprint?
public class Fibonacci {
/**
* time:2012.12.2
* author:王金宇
* description:用遞歸實現斐波那契數列，但是此方法是嫉妒危險的，適用于求解比較小的位置數值
*/
public static void main(String[] args) {
Fibonacci fibonacci=new Fibonacci();
int result=fibonacci.fib(5);
System.out.println(result);
}
public int fib(int index){
if(index==1||index==2){
return 1;
}else{
return fib(index-1)+fib(index-2);
}
}
}
public class Fibonacci {
/**
* time:2012.12.2
* author:王金宇
* description:用遞歸實現斐波那契數列，但是此方法是嫉妒危險的，適用于求解比較小的位置數值
*/
public static void main(String[] args) {
Fibonacci fibonacci=new Fibonacci();
int result=fibonacci.fib(5);
System.out.println(result);
}
public int fib(int index){
if(index==1||index==2){
return 1;
}else{
return fib(index-1)+fib(index-2);
}
}
}
程序分析：這個實例是非常經典的實例，主要是利用遞歸實現了Fibonacci數列。這個遞歸算法的出口是在
[java] view plaincopyprint?
if(index==1 || index==2){
return 1;
}
if(index==1 || index==2){
return 1;
}
這個代碼段上，如果程序的index符合條件就會停止進行遞歸。所以這個程序的運行流程是：
剛才說了這個方法十幾度危險的，為什么這么說，原因在于在這個遞歸里做了冗余的工作，如圖，我們在f4里面已經計算了f2，可是f3里有同樣計算了f2，以此類推那些冗余的工作，在數值比較小的情況下，計算機還是可以接受的。但是，當求解的數值比較大，它是成指數級增長的，所以不要再遞歸中做重復的工作。
?、趎的階乘
問題描述：求5的階乘
求解代碼：
[java] view plaincopyprint?
public class Factorial_Five {
/**
* time:2012.12.2
* author:王金宇
* description:遞歸求n的階乘
*/
public static void main(String[] args) {
Factorial_Five factorial_Five=new Factorial_Five();
int result=factorial_Five.factorial(5);
System.out.println(result);
}
public int factorial(int index){
if(index==1){
return 1;
}else{
return factorial(index-1)*index;
}
}
}
public class Factorial_Five {
/**
* time:2012.12.2
* author:王金宇
* description:遞歸求n的階乘
*/
public static void main(String[] args) {
Factorial_Five factorial_Five=new Factorial_Five();
int result=factorial_Five.factorial(5);
