遞歸常用來解決一些可拆分的嘿架，并且拆分到一定程度自然得到解的問題瓶珊，最經(jīng)典的就是斐波那契數(shù)列（1，1耸彪，2伞芹，3，5......）蝉娜，從第三個數(shù)開始唱较，每個數(shù)的值都為前面兩個數(shù)的和，如第五個數(shù)字等于第三個數(shù)字加上第四個數(shù)字的和召川，第N個等于第N-1個數(shù)字加上第N-2數(shù)字的和
public static int Fibonacci(int n) {
if (n == 1) {
return 1;
}
if (n == 2) {
return 1;
}
return Fibonacci(n-1)+Fibonacci(n-2);
代碼看起來很簡單绊汹，實際上效率很低，當我們計算的數(shù)據(jù)很大的時候扮宠，比如第五十位數(shù)，會進行非常多次的分解，如果將運行的順序抽象為一張類似二叉樹的圖的話坛增，就能清晰的看到這種直接遞歸的缺點
圖片.png
計算數(shù)列第五位數(shù)字的時候获雕，運行的步驟是這樣的，可以看到重復了兩次第三位的結果收捣，隨著位數(shù)的增加届案，重復的計算也會急劇上升，我們可以通過一個數(shù)組或者集合來保存我們計算過的數(shù)據(jù)罢艾，遇到重復的計算的時候直接從集合中獲取
public static int Fibonacci(int n) {
int memo[]=new int[n+1];
return Fibonacci(n,memo);
}
public static int Fibonacci(int n,int [] memo) {
if (memo[n]>0){
return memo[n];
}
if (n==1){
return 1;
}
else if (n==2){
return 1;
}else {
memo[n]=Fibonacci(n-1,memo)+Fibonacci(n-2,memo);
}
return memo[n];
}
這樣的話楣颠，我們的計算效率就會提高很多了
